Очередная задачка с codewars

(0) Вам скучно и одиноко
Не, чувак, это тебе - скучно и одиноко. Все кончится опять твоим вяленьким "вечерком сравню по времени выполнения", как в Оптимальное решение задачки

(0) в случае четного n почему начало отсчёта берётся так как на рисунке?

(2) а не... Там наоборот внутрь идут

вообще по идее можно в 1 цикле сделать

Ну короче, там всё время два прохода одной длины. Потом длина уменьшается на 1. Между проходами поворот. В первый раз три прохода.

(4) >  при большом массиве покупателей
О. А давай-ка ты и для этой задачи, превентивно, какие-нибудь условия озвучишь.

(11) Не пойдет. Я сейчас напишу тебе красивое и быстрое решение на каких-нибудь битовых операциях и услышу в ответ нудятину "а вот оно на больших размерностях..."

(7) https://www.haikson.com/programmirovanie/zapolnenie-dvumernoj-matritsyi-po-spirali/
Заменяешь присвоение a[i][j] = k; на вывод этого a[i][j] и все

инициализируем
delta=1

x=-1
y=0
lxy=n
  
крутим цикл
while (lxy>0){
  for(i=0;i<lxy;i++){
    x+=delta
    print Массив[x,y]
  }
  lxy--
  if(lxy>0){
    for(i=0;i<lxy;i++){
      y+=delta
      print Массив[x,y]
    }
  }
  delta=-delta
}

+(17) Хотя if не нужен, все равно в цикл не зайдет

Запрос = Новый Запрос;
    Запрос.Текст =
    "ВЫБРАТЬ 1 КАК x, 0 КАК y
    |ОБЪЕДИНИТЬ ВСЕ ВЫБРАТЬ    0, 1
    |ОБЪЕДИНИТЬ ВСЕ ВЫБРАТЬ    -1, 0
    |ОБЪЕДИНИТЬ ВСЕ ВЫБРАТЬ    0, -1";
    
    Векторы = Запрос.Выполнить().Выгрузить();
    
    Слоев = Цел(N/2);
    
    НомерЯчейки = 0;
    Для Слой = 1 По Слоев Цикл
        Тек = Новый Структура("x,y", Слой, Слой);
        Для каждого Направление Из Векторы Цикл
            Для инд = 1 По N+1-2*Слой  Цикл
                НомерЯчейки = НомерЯчейки + 1;
                ТД.Область(тек.y, тек.x).Текст = НомерЯчейки;
                тек.x = тек.x + Направление.x;
                тек.y = тек.y + Направление.y;
            КонецЦикла;
        КонецЦикла;
    КонецЦикла;
    
    Если N%2=1 Тогда
        НомерЯчейки = НомерЯчейки + 1;
        ТД.Область((N+1)/2, (N+1)/2).Текст = НомерЯчейки;
    КонецЕсли;

(20) Да, конечно нужно одну строку поменять
ТД.Область(тек.y, тек.x).Текст = НомерЯчейки;
на
МассивЛинейный[НомерЯчейки-1] = МассивКвадратный[тек.y-1][тек.x-1];//вомзожно x и y нужно поменять местами

Хотелось без "если" обойтись, но не получилось)

Самый простой вариант - создаём массив битов,равный нашему массиву.
Когда проходим точку,то устанавливаем бит.
Далее,определяем смещение по x и y для перехода в следующую точку.
Прежде чем шагнуть,проверяем,а не занята ли она,если занята,то меняем вектор смещения поворотом по часовой стрелке.
Когда сразу после поворота снова будет занято,то мы прошли весь массив.

(15) вот зачем писать такой стрёмный код? Хотя бы разбей метод на подметоды

(25) код стал короче, но не стал понятнее. Низачот

тут 4 цикла по ребрам и 1 общий цикл по числу кругов

(0) Простейший КА же

(28)+ Две переменные нужны номер шага и направление исполнителя и текущие координаты x, y
Изначально шаг = 0, направление 1 (принимаем что 0 - вверх, 1 вправо, 2 вниз, 3 влево), координаты 0,0 левый верхний угол
Далее на каждом шагу считываем текущее значение x,y из массива, если можно то перемещаемся на 1 шаг в текущем направлении, пройденную ячейку массива помечаем как то (можно новым массив NxN завести или в текущий нечто писать)
Если упираемся в "стену" (границы массива или уже пройденное значение) то сначала поворот на 90 по часовой а затем уже шаг перед, если и там стена то снова поворот
Как уже некуда идти после поворотов то стоп

[1с]
// хехе... вариант вообще без циклов )))
Функция ПолучитьМассивПоЗмейке( ДвуМерныйМассив , Знач ТекНомерКруга = -1, Знач ТекСтрока = -1, Знач ТекСтолбец = -1 , ТекущийСписокЗначений = Неопределено )
    Если ТекНомерКруга < 0 Тогда
        ТекущийСписокЗначений = Новый СписокЗначений;
        Возврат ПолучитьМассивПоЗмейке(ДвуМерныйМассив,0,0,0,ТекущийСписокЗначений);
    КонецЕсли;
    ТекИндексМин = ТекНомерКруга;
    ТекИндексМакс = ДвуМерныйМассив.ВГраница()-ТекИндексМин;
    ТекущийСписокЗначений.Добавить( ДвуМерныйМассив[ТекСтрока][ТекСтолбец] );
    Если ТекНомерКруга < ДвуМерныйМассив.ВГраница()/2 Тогда
        Если ТекСтрока = ТекИндексМин Тогда
            Если ТекСтолбец < ТекИндексМакс Тогда
                ТекСтолбец = ТекСтолбец + 1;
            Иначе
                ТекСтрока = ТекСтрока + 1;
            КонецЕсли;
        ИначеЕсли ТекСтолбец = ТекИндексМакс Тогда
            Если ТекСтрока < ТекИндексМакс Тогда
                ТекСтрока = ТекСтрока + 1;
            Иначе
                ТекСтолбец = ТекСтолбец - 1;
            КонецЕсли;
        ИначеЕсли ТекСтрока = ТекИндексМакс Тогда
            Если ТекСтолбец > ТекИндексМин Тогда
                ТекСтолбец = ТекСтолбец - 1;
            ИначеЕсли ТекСтрока - 1 >ТекИндексМин Тогда
                ТекСтрока = ТекСтрока - 1;
            Иначе
                Возврат ТекущийСписокЗначений.ВыгрузитьЗначения();
            КонецЕсли;
        ИначеЕсли ТекСтолбец = ТекИндексМин Тогда
            Если ТекСтрока > ТекИндексМин + 1 Тогда
                ТекСтрока = ТекСтрока - 1;
            ИначеЕсли ТекНомерКруга < ДвуМерныйМассив.ВГраница()/2 Тогда
                ТекНомерКруга = ТекНомерКруга + 1;
                ТекСтрока = ТекНомерКруга;
                ТекСтолбец = ТекНомерКруга;
            Иначе
                Возврат ТекущийСписокЗначений.ВыгрузитьЗначения();
            КонецЕсли;
        КонецЕсли;
        Возврат ПолучитьМассивПоЗмейке( ДвуМерныйМассив , ТекНомерКруга , ТекСтрока, ТекСтолбец, ТекущийСписокЗначений);
    КонецЕсли;
    Возврат ТекущийСписокЗначений.ВыгрузитьЗначения();
КонецФункции //ПолучитьМассивПоЗмейке
[/1с]

(30) эм... Хуже такого кода разве что вот такой:
https://www.govnokod.ru/1777

и мозг сломаешь, пытаясь понять логику работы кода, и для трудновыявляемых ошибок благодатная среда

Процедура ВыводМассиваИсточник(ВысотаМасива, ДлинаМасива, МассивИсточник)
    
    
    Для НомВысота = 1 по ВысотаМасива Цикл
        ТекСтрока = "";
        Для НомДлина = 1 по ДлинаМасива Цикл
            
            ТекЗначСтр = СокрЛП(МассивИсточник[НомДлина - 1][НомВысота - 1]);
            
            ТекСтрока = ТекСтрока + ЛЕв("          ", 5 - СтрДлина(ТекЗначСтр))+  ТекЗначСтр +"; ";
        КонецЦикла;
        Сообщить(ТекСтрока);
    КонецЦикла;
    
    
КонецПроцедуры


Процедура ВыводМассиваРезультат(ВысотаМасива, ДлинаМасива, МассивРезультат)
    
    
        ТекСтрока = "";
        Для НомДлина = 1 по ДлинаМасива*ВысотаМасива Цикл
            
            ТекЗначСтр = СокрЛП(МассивРезультат[НомДлина - 1]);
            
            ТекСтрока = ТекСтрока + ЛЕв("          ", 5 - СтрДлина(ТекЗначСтр))+  ТекЗначСтр +"; ";
        КонецЦикла;
        Сообщить(ТекСтрока);
    
    
    
КонецПроцедуры



ДлинаМасива = 5;
ВысотаМасива = 5;


МассивИсточник = Новый Массив(ДлинаМасива, ВысотаМасива);

МассивРезультат = Новый Массив(ДлинаМасива * ВысотаМасива);


НаправлениеДвиженияГоризнотальное = Истина;

ТекСтолбец = 0;
ТекСтрока = 1;

НаправлениеДвиженияПоДлине = 1;
НаправлениеДвиженияПоВысоте = 1;

ПройденоКолец = 0;


Для НомПП = 1 По  ДлинаМасива * ВысотаМасива Цикл
    Если НаправлениеДвиженияГоризнотальное Тогда
        
        ТекСтолбец = ТекСтолбец + НаправлениеДвиженияПоДлине;
        
        
        Если (НаправлениеДвиженияПоДлине > 0 и ТекСтолбец = ДлинаМасива - ПройденоКолец ) или
            (НаправлениеДвиженияПоДлине < 0 и ТекСтолбец = 1 + ПройденоКолец)
            
            Тогда
            НаправлениеДвиженияГоризнотальное = не НаправлениеДвиженияГоризнотальное;
            
            НаправлениеДвиженияПоДлине = - НаправлениеДвиженияПоДлине;
            
            Если НаправлениеДвиженияПоДлине >0 ТОгда
                ПройденоКолец = ПройденоКолец +1;
            КонецЕСли;
        КонецЕСли;
    Иначе
        ТекСтрока = ТекСтрока + НаправлениеДвиженияПоВысоте;
        
        Если  (НаправлениеДвиженияПоВысоте > 0 и ТекСтрока = ВысотаМасива - ПройденоКолец ) или
            (НаправлениеДвиженияПоВысоте < 0 и ТекСтрока = 1 + ПройденоКолец)
            
            Тогда
            НаправлениеДвиженияГоризнотальное = не НаправлениеДвиженияГоризнотальное;
            
            НаправлениеДвиженияПоВысоте = - НаправлениеДвиженияПоВысоте;
            
        КонецЕСли;
    КонецЕСли;
    
    МассивИсточник[ТекСтолбец - 1][ТекСтрока - 1] = НомПП;
    
    
    МассивРезультат[ДлинаМасива * ВысотаМасива - НомПП] = НомПП;
КонецЦикла;

ВыводМассиваИсточник(ВысотаМасива, ДлинаМасива, МассивИсточник);

Сообщить(" ");

ВыводМассиваРезультат(ВысотаМасива, ДлинаМасива, МассивРезультат);

(0) Решение на JS. Проверка граничных условий получилась довольно длинная, вынес в отдельные функции checkX и checkY:

function snail(a) {
    let x = -1, y = dy = 0, dx = 1, res = [], n = a.length;
    const checkX = () => dx === 0 || x + dx !== (dx > 0 ? n - y : n - y - 2);
    const checkY = () => dy === 0 || y + dy !== (dy > 0 ? x + 1 : x);

    do {
        do {
            res.push(a[y += dy][x += dx]);
        } while(checkX() && checkY());
        [dy, dx] = [dx, -dy];
    } while (checkX() && checkY())
    
    return res;
}

+(33) Заметьте, без каких-либо счетчиков циклов. Чистая логика. Сам себе решил усложнить задачу, иначе слишком легко и не интересно

С рекурсией





Процедура ВыводМассиваИсточник(ВысотаМасива, ДлинаМасива, МассивИсточник)
    
    
    Для НомВысота = 1 по ВысотаМасива Цикл
        ТекСтрока = "";
        Для НомДлина = 1 по ДлинаМасива Цикл
            
            ТекЗначСтр = СокрЛП(МассивИсточник[НомДлина - 1][НомВысота - 1]);
            
            ТекСтрока = ТекСтрока + ЛЕв("          ", 5 - СтрДлина(ТекЗначСтр))+  ТекЗначСтр +"; ";
        КонецЦикла;
        Сообщить(ТекСтрока);
    КонецЦикла;
    
    
КонецПроцедуры


Процедура ВыводМассиваРезультат(ВысотаМасива, ДлинаМасива, МассивРезультат)
    
    
    ТекСтрока = "";
    Для НомДлина = 1 по ДлинаМасива*ВысотаМасива Цикл
        
        ТекЗначСтр = СокрЛП(МассивРезультат[НомДлина - 1]);
        
        ТекСтрока = ТекСтрока + ЛЕв("          ", 5 - СтрДлина(ТекЗначСтр))+  ТекЗначСтр +"; ";
    КонецЦикла;
    Сообщить(ТекСтрока);
    
    
    
КонецПроцедуры



Процедура ЗаполнитьПолниМассив(МассивИсточник, МассивРезультат = Неопределено, НомПП = 0, струкДвижения = Неопределено, ПройденоКолец = 0, ИмяТекКоординаты = "ТекСтолбец", ИмяТекГраницы = "ДлинаМасива", НаправлениеДвижения = 1)
    
    Если  НомПП >  струкДвижения.ВысотаМасива * струкДвижения.ДлинаМасива Тогда
        Возврат;
    КонецЕСли;
    
    
    струкДвижения[ИмяТекКоординаты] = струкДвижения[ИмяТекКоординаты] + НаправлениеДвижения;
    
    Если  (НаправлениеДвижения > 0 и струкДвижения[ИмяТекКоординаты] = струкДвижения[ИмяТекГраницы] - ПройденоКолец ) или
        (НаправлениеДвижения < 0 и струкДвижения[ИмяТекКоординаты] = 1 + ПройденоКолец) Тогда
        
        
        Если  ИмяТекКоординаты = "ТекСтрока" Тогда
            НаправлениеДвижения = - НаправлениеДвижения;
            Если  НаправлениеДвижения > 0 Тогда
                ПройденоКолец = ПройденоКолец +1;
                струкДвижения.ТекСтолбец = струкДвижения.ТекСтолбец + 1;
                струкДвижения.ТекСтрока = струкДвижения.ТекСтрока + 1;
                
            КонецЕСли;
        КонецЕСли;
        
        ИмяТекКоординаты = ?(ИмяТекКоординаты = "ТекСтолбец", "ТекСтрока", "ТекСтолбец" );
        ИмяТекГраницы = ?(ИмяТекГраницы = "ДлинаМасива", "ВысотаМасива", "ДлинаМасива" );
    КонецЕСли;
    
    МассивИсточник[струкДвижения.ТекСтолбец - 1][струкДвижения.ТекСтрока - 1] = НомПП;
    
    МассивРезультат[струкДвижения.ДлинаМасива * струкДвижения.ВысотаМасива - НомПП] = МассивИсточник[струкДвижения.ТекСтолбец - 1][струкДвижения.ТекСтрока - 1];
    
    
    ЗаполнитьПолниМассив(МассивИсточник, МассивРезультат, НомПП+ 1, струкДвижения, ПройденоКолец,
    ИмяТекКоординаты, ИмяТекГраницы,
    НаправлениеДвижения)    
    
    
КонецПроцедуры



Функция ПолучитьМассивПоЗмейке(МассивИсточник)
    
    
    
    струкДвижения = Новый Структура;
    струкДвижения.Вставить("ТекСтолбец", 0);
    струкДвижения.Вставить("ТекСтрока", 1);
    
    струкДвижения.Вставить("ВысотаМасива", 0);
    струкДвижения.Вставить("ДлинаМасива", 0);
    
    Попытка
        струкДвижения.ВысотаМасива = МассивИсточник.Количество();
        струкДвижения.ДлинаМасива = МассивИсточник[0].Количество();
    Исключение
        Сообщить("Чёт, не похоже на двумерный массив.");
        Возврат Новый Массив(1);
    КонецПопытки;
    
    МассивРезультат = Новый Массив(струкДвижения.ДлинаМасива * струкДвижения.ВысотаМасива);
    
    НомПП = 1;
    
    ЗаполнитьПолниМассив(МассивИсточник, МассивРезультат, 1, струкДвижения, 0,
    "ТекСтолбец", "ДлинаМасива",     1);    
    
    Возврат  МассивРезультат;
    
КонецФункции


ДлинаМасива = 5;
ВысотаМасива = 5;


МассивИсточник = Новый Массив(ДлинаМасива, ВысотаМасива);

МассивРезультат = ПолучитьМассивПоЗмейке(МассивИсточник);


ВыводМассиваИсточник(ВысотаМасива, ДлинаМасива, МассивИсточник);

Сообщить(" ");

ВыводМассиваРезультат(ВысотаМасива, ДлинаМасива, МассивРезультат);

(35) Поправка


        струкДвижения.ДлинаМасива = МассивИсточник.Количество();
        струкДвижения.ВысотаМасива = МассивИсточник[0].Количество();

еще вариант автокода))

    Массив = ПолучитьМассив(); // задаваемый массив
    хмакс = Массив.ВГраница();
    умакс = хмакс;
    хмин = 0;
    умин = 0;
    угол = 0;
    х = 0;
    у = 0;
    МассивРезультат = Новый Массив;
    Пока Истина Цикл
        МассивРезультат.Добавить(Массив[у][х]);
        Если угол = 0 Тогда
            Если х = хмакс Тогда
                угол = 1;
                умин = умин + 1;
                у = умин;
            Иначе
                х = х + 1;
            КонецЕсли;
        ИначеЕсли угол = 1 Тогда
            Если у = умакс Тогда
                угол = 2;
                хмакс = хмакс - 1;
                х = хмакс;
            Иначе
                у = у + 1;
            КонецЕсли;
        ИначеЕсли угол = 2 Тогда
            Если х = хмин Тогда
                угол = 3;
                умакс = умакс - 1;
                у = умакс;
            Иначе
                х = х - 1;
            КонецЕсли;
        ИначеЕсли угол = 3 Тогда
            Если у = умин Тогда
                угол = 0;
                хмин = хмин + 1;
                х = хмин;
            Иначе
                у = у - 1;
            КонецЕсли;
        КонецЕсли;
        Если умин > умакс
            Или хмин > хмакс Тогда
            Прервать;
        КонецЕсли;
    КонецЦикла;

(31) спасибо ваше мнение очень важно для нас (с) lol
если мозгов не хватает понять обычную рекурсию и элементарную арифметику - так работайте над собой а не нойте про говнокод. )))

(38) 一个小气的财主叫他的仆人去买酒，但是没有给他钱。仆人说：“老爷，没有钱怎么能够买酒呢？”财主生气地说：“用钱买酒谁不会？不用钱买到酒才算真的能干呢！”
过了一会儿，仆人拿着空瓶子回来了。主人大骂：“你叫我喝什么？”仆人说：“瓶子里没有酒，谁不会喝！要是能从空瓶子里喝出酒来，那才算真的能干呢！”

если мозгов нет понять иероглифы, так работайте над собой. Код пишется для людей, а не для компилятора. Хороший код должен быть максимально линейным и понятным. А не состоять из шарад в виде рекурсий

Всё просто. Допустим, написал ты 100 строк кода. Другому программисту нужно внести небольшие изменения в этот код:

- если программист за 2 минуты понял всю логику кода и сразу же нашел место правки - у тебя хороший код
- если программисту понадобилось полчаса ползать с отладчиком по твоему коду - у тебя дрянной код

Код в (30) и (37) выдает ошибку даже на массиве 3×3.Можно дальше не смотреть.

(41) А в (17)?

(41): врете, код в (30) скопирован из рабочей обработки и не дает ошибок.
жду извинений.

(43) Извиняюсь, код (30) правильно работает до массивов 40x40, даже меньше. Код (37) работает без проблем и на массиве 100x100.Что впрочем и понятно - нерекурсивный.Можно написать еще проще.

(0) Это вот то самое, что ты хотел добиться - локального срачика?

(42) (17)Работает, но наоборот - против часовой стрелки раскручивает.

(46) А... ясно, Массив[x,y] - неправильно, надо везде поменять на Массив[y,x] - первым идет номер слоя (т.е. координата y), а вторым - позиция элемента в этом слое (т.е. координата x)

(44) >> Код (37) работает без проблем и на массиве 100x100

Как-то слабовато. Щас проверил код из (33), на массиве 10000х10000 отработал за несколько секунд в браузере Эдж. В Хроме или в Ноде должен еще быстрее.

Немного оптимизировал по времени выполнения
Максимальный размер массива получился 46340 х 46340, выборал исходя из размера занимаемой памяти, чтобы входной и выходной массивы были примерно по 2 гигабайта. Браузер не дает выделять больше памяти.

На тестовом массиве функция выполняется за пол минуты в Microsoft Edge. В хроме не пробовал, лень устанавливать. Проверьте у кого есть.

function snail(a) {
    let x = -1, y = dy = resIndex = 0, dx = 1;
    const n = a.length;
    const res = new Uint8Array(n * n);

    for (let l = n - .5; l; l -= .5) {
        for (let i = 0; i < l; i++)
            res[resIndex++] = a[y += dy][x += dx];
        [dy, dx] = [dx, -dy];
    };

    return res;
}

+51 ограничение - память 65535, время - 1000мс

(52) >> количество селений (1 <= n <= 100000)
>> ограничение - память 65535
>> Для хранения ответа используйте список, где индекс будет номером селения

Что-то тут не сходится...

(53) вот тут я хз, но мое решение работает, только по времени исполнения ошибку выдает...

(51) А как делал?

Если идти по подсказке, то:
1) сортируем список селений и бомбоубежищ
2) Допустим мы рассмотрели селение i, и для него нашли ближайшее убежище j. Теперь берем следующее селение i+1 и для него надо быстро найти ближайшее бомбоубежище. Оно будет либо полученное на предыдущем шаге (j), либо какое-то из последующих (j...n)
3) Используем Метод половинного деления, т.е. берем середину нашего отрезка k=(j+n)/2 и смотрим - селение находится ближе или дальше этой середины. Если ближе, то рассматриваем диапазон (j...k), если дальше, то диапазон (k...n).
P.S. Мне лениво разбираться, когда остается 1-2 элемента, поэтому если в выборке осталось менее 5 элементов, то я делаю просто полный перебор, все равно это выгоднее, чем перебирать все 100000 элементов.

(49) Норм. В (17) почти тоже самое, но у тебя доведено. Вероятно, оптимальный вариант. Только пляски с 0.5 - ну, такое... Вкусовщина, но лично я не одобрям.

(48) Хм..Как то тоже слабовато.Массив 100000x 100000 ( 10 в 10 степени ячеек) основное время - заполнение первоначального массива. Сама процедура, без вывода результата ;-) - мгновенно.
Полное время 1 минута 47 с.
А сколько времени в браeзере занимает вывод массива 40000x40000?

(56) 0.5 мне тоже не очень, можно было заменить на какой-то флаг и добавить пару условий и дополнительных действий, но это мало влияет, так что не стал.

(57) Странно. У меня первоначальный массив заполнялся гораздо быстрее чем основная процедура. Ты как заполнял?
Вывод массива в браузер не происходит, не стал это оформлять в какой-то формат или HTML. Результат выполнения функции возвращается в консоль, его можно посмотреть в виде массива в удобном виде.

100000x100000 - мгновенно? Не верю что-то.

(55) В третьем пункте не нужен двоичный поиск. Нужно просто для каждого селения i двигать вправо j пока расстояние между селением i и бомбоубежищем j уменьшается.

(61) В самой задаче уже все расписано как ее делать. Так не интересно.

(61) Ну... автор этой темы в (54) говорит, что у него не проходит алгоритм по времени.

(63) Проверил этот алгоритм на JS в браузере, результат вполне быстрый, ~200 миллисекунд на максимальных размерах массивов:

function bomb(cities, vaults) {
    const [ sortedCities, sortedVaults ] = [ cities, vaults ].map(coords => Object.entries(coords).sort((a, b) => a[1] - b[1]))
    let vaultIndex = 0;
    const vaultsCount = vaults.length;
    const ret = new Uint32Array(cities.length);

    sortedCities.map(city => {
        const cityCoord = city[1];
        let closestDisd = Math.abs(cityCoord - sortedVaults[vaultIndex][1]);
        let nextDist;
        while (vaultIndex + 1 < vaultsCount && (nextDist = Math.abs(cityCoord - sortedVaults[vaultIndex + 1][1])) < closestDisd) {
            vaultIndex++;
            closestDisd = nextDist;
        }
        ret[city[0]] = +sortedVaults[vaultIndex][0] + 1;
    });

    return ret;
}

Причем самая долгая операция - это сортировка в самой первой строке: ~180 миллисекунд.
Основной цикл выполняется в среднем за 20-25 миллисекунд.

Как я понимаю, суть задачи - это написать свою более быструю функцию сортировки. В ней как раз узкое место. Но мы, конечно, этого делать не будем, потому что это уже делали на лабораторных работах в ВУЗе, ничего интересного, все уже давно придумано.

(63) Да, но судя по всему у него как-то не так реализован последний шаг, потому что и вариант с двоичным поиском, и вариант с просто продвижением второго указателя (который практически полностью описан в самом условии) должны быть достаточны для такого размера входных данных. Более того с этими двумя вариантами самым затратным шагом будет все равно является сортировка.

Почему я сказал, что двоичный поиск не нужен. Смотрите, если мы делаем двоичный поиск для каждого селения, то сложность этой части алгоритма в худшем случае (а при решении таких задачек нас ведь интересует именно худший случай в отличие от реальной жизни) будет O(n*log(m)), сложность варианта с продвижением второго указателя - O(n+m), так как мы идем всегда только вправо и за весь внешний цикл в худшем случае просто пройдем весь массив бомбоубежищ. Второй вариант при данных ограничениях будет быстрее. Вариант с двоичным поиском имеет, конечно, право на существование, когда m на порядки больше n, тогда мы исключаем линейную зависимость от количества бомбоубежищ. Но все это довольно бесполезно анализировать, когда у нас первый шаг - это сортировка обоих массивов, которая уже сама по себе будет иметь сложность O(n*log(n) + m*log(m)), что и будет являться самой затратной по времени частью алгоритма.

Вообще, эта задачка - достаточно классический пример two pointers technique. И ее основной смысл обычно в демонстрации этой незамысловатой техники.