Усовершенствовать решение задачи "Муравьи-мутанты" - Free Pascal

Формулировка задачи:

Всем привет. Написала код к задаче "Муравьи-мутанты", но он не проходит некоторые тесты по времени. Подскажите, пожалуйста, как можно его усовершенствовать? Заранее спасибо.

Цикл Интернет-олимпиад для школьников, сезон 2014-2015 Четвертая личная олимпиада, 14 февраля 2015 года

Задача A. Муравьи-мутанты

Имя входного файла: ant.in Имя выходного файла: ant.out Ограничение по времени: 2 секунды Ограничение по памяти: 256 мегабайт В городе, который так бережно оберегал Человек-паук, появились муравьи. И это не просто маленькие милые насекомые. Это огромные кровожадные мутанты! Человек-паук, как обычно, не стал доверять очистку города местной полиции и решил принять удар на себя. Известно, что муравьи-мутанты двигаются по координатной прямой. В начальный момент времени координата i-го муравья равна a_i. Каждую секунду муравьи перемещаются на одну позицию вправо. То есть, если в данный момент муравей находится в точке x, то через секунду он будет находиться в точке x + 1. Чтобы расправиться со злобными тварями, Человек-паук расставил ловушки на этой самой прямой. Причем i-я ловушка находится в позиции b_i. Когда муравей оказывается в точке, в которой находится ловушка, ловушка срабатывает и обездвиживает муравья. Одна ловушка может захватить не более одного муравья. Можно считать, что как только муравей попал в ловушку, эти муравей и ловушка перестают существовать. Человеку-пауку стало интересно, в какую ловушку попал каждый муравей. Помогите Человеку-пауку, он в долгу не останется!

Формат входного файла

В первой строке входного файла даны два числа n, m (1 ≤ n ≤ 100000; 1 ≤ m ≤ 100000) - количество муравьев и ловушек соответственно. В следующей дано n чисел a_i (0 ≤ a_i ≤ 10⁹) - координата i-го муравья. Гарантируется, что a_i < a_i+1 для всех 1 ≤ i < n. В следующей дано m чисел b_i (0 ≤ bi ≤ 10⁹) - координата i-й ловушки. Гарантируется, что b_i < b_i+1 для всех 1 ≤ i < m.

Формат выходного файла

В выходной файл выведите n строк. В i-й строке выведите номер ловушки, в которую попадет i-й муравей. Муравьи и ловушки нумеруются с единицы в том порядке, в котором они даны во входном файле. Если муравей не попадет ни в какую ловушку, в i-й строке выходного файла выведите -1.

Пример

ant.in	ant.out
8 6 0 2 3 4 5 6 8 13 1 3 5 6 9 12	1 -1 2 6 3 4 5 -1

Система оценивания

Первая группа тестов состоит из тестов, для которых выполняются ограничения n ≤ 100, m ≤ 100. Баллы за эту группу начисляются только при прохождении всех тестов группы. Стоимость группы составляет 50 баллов. Вторая группа тестов состоит из тестов, для которых выполняются ограничения n ≤ 100000, m ≤ 100000. Баллы за эту группу начисляются только при прохождении всех тестов группы. Стоимость группы составляет 50 баллов. Обратите внимание на возможность узнать результат проверки вашего решения на всех группах тестов, нажав на ссылку "Request feedback" на вкладке "Runs".

Program Muravey;
Var a,b,i1:array[1..100000] of longint; i,j,i2,j1,m,n,min,k:longint; f1,f2:text;
Begin
assign(f1,'ant.in');
reset(f1);
readln(f1,n,m);
for i:=1 to n do read(f1,a[i]);
for i:=1 to m do read(f1,b[i]);
close(f1);
for i:=1 to n do i1[i]:=-1;
for k:=1 to m do
begin
 min:=1000000000;
 for i:=1 to m do
  if (b[i]<>-1) then
  begin
  for j:=1 to n do
      if (a[j]<>-1)  then
       begin
       if (a[j]<=b[i]) then
        if abs(b[i]-a[j])<=min then
        begin
         min:=abs(b[i]-a[j]);
         i2:=i;
         j1:=j;
        end;
       end;
  end;
 b[i2]:=-1;
 a[j1]:=-1;
 i1[j1]:=i2;
end;
assign(f2,'ant.out');
rewrite(f2);
for i:=1 to n do writeln(f2,i1[i]);
close(f2);
End.

Решение задачи: «Усовершенствовать решение задачи "Муравьи-мутанты"»

Листинг программы

#include <bits/stdc++.h>
 
int main()
{
    std::ios_base::sync_with_stdio(0);
    
    std::ifstream fin("ant.in");
    std::ofstream fout("ant.out");
    
    std::vector<int> a;
    std::set<int> b;
    std::unordered_map<int, int> b_id;
    int n, m, x;
        //чтение данных
    fin >> n >> m;
    
    for(int i = 0; i < n; i++)
    {
        fin >> x;
        a.push_back(x);
    }
    
    for(int i = 0; i < m; i++)
    {
        fin >> x;
        b.insert(x);
        b_id[x] = i;
    }
    
    int ans;
    std::set<int>::iterator it;
    for(int i = n - 1; i >= 0; i--) //Идем циклом по муравьям от последнего до первого
    {
        ans = -1;
        it = b.lower_bound(a[i]); //ищем самую ближнюю ловушку за O(log(m))
        if(it != b.end()) //нашли?
        {
            ans = b_id[*it]; //находим её номер за О(1) в хеш-таблице
            ans++; //увеличиваем номер ловушки на 1, т.к они у меня нуль-индексированые
            b.erase(*it); //удаляем ловушку за O(log(m))
        }
        a[i] = ans; //запоминаем ответ
    }
    
        //выводим все ответы
    for(int i = 0; i < n; i++)
    {
        fout << a[i] << std::endl;
    }
    
    fin.close();
    fout.close();
    
    return 0;
}

Объяснение кода листинга программы

Включаем заголовочный файл <bits/stdc++.h> для использования библиотеки iostream.
Объявляем функцию main().
Блокируем синхронизацию ввода-вывода с помощью std::ios_base::sync_with_stdio(0).
Открываем файлы fin и fout для чтения и записи соответственно.
Создаем пустой вектор a для хранения значений муравьев.
Создаем пустой набор b для хранения ловушек.
Создаем пустой хеш-код b_id для хранения соответствия между ловушками и их номерами.
Считываем из файла значения n и m.
Заполняем вектор a значениями муравьев.
Заполняем набор b и хеш-код b_id значениями ловушек.
Инициализируем переменную ans значением -1.
Инициализируем итератор it для набора b с помощью функции std::set::iterator it = b.lower_bound(a[i]);.
Проверяем, найдена ли ловушка для текущего муравья, сравнивая итератор it с концом набора b (b.end()).
Если ловушка найдена, то находим её номер в хеш-коде b_id и увеличиваем его на 1 (у нас нуль-индексированные ловушки).
Удаляем найденную ловушку из набора b с помощью функции b.erase(*it).
Запоминаем найденный номер ловушки в качестве ответа для текущего муравья в векторе a.
Выводим все ответы, перебирая элементы вектора a и записывая их в файл fout с помощью функции fout << a[i] << std::endl.
Закрываем файлы fin и fout с помощью функций fin.close() и fout.close().
Возвращаем 0, чтобы указать, что программа успешно завершилась.
Ввод и вывод данных в формате текстового файла осуществляется через стандартный поток ввода-вывода (std::cin и std::cout).