C/C++

Как оптимизировать код, чтобы не было превышения по времени к задаче (C++)?

Задача (на изображении). Я написал к ней код, но он не проходит по времени (на втором тесте). Хотел спросить, как оптимизировать код или, может быть, есть другой алгоритм, который эффективнее моего? Мой код на C++ -
https://pastebin.com/1nJBsg1X. Заранее благодарю.
ДД
Димка Друг
200
А так попробуйте!

#include <iostream>
#include <map>
#include <set>
using namespace std;
int main() {
size_t n;
cin >> n;
map<unsigned, int> box;
set<int> seq;
int val;
cin >> val;
seq.insert(val);
for (auto i = 1U; i < n; ++i) {
cin >> val;
for (const auto itm : seq) ++box[abs(itm - val)];
seq.insert(val);
}
size_t q;
cin >> q;
unsigned len;
for (auto i = 0U; i < q; ++i) {
cin >> len;
cout << box[len] << '\n';
}
system("pause > nul");
}
ТТ
Туман Туманский
63 532
Лучший ответ
Димка Друг Спасибо огромное. Правда, к сожалению, пока что есть проблема с превышением ограничения по времени. Это задание относится, если не ошибаюсь, к теме "Быстрое деление. Fast subset convolution и многомерное преобразование Фурье", но я, наверное, не очень понимаю, как можно было бы применить эту тему к этой задаче, хотя, возможно, именно с помощью нее можно сделать оптимальный по времени код.
Сортировка вообще не нужна.

const int MAX = 100001;
int a[MAX] = {0};
char b[2 * MAX] = {0};

int main(void) {
int n;
cin >> n;
for (int i = 0; i < n; ++i) { cin >> a[i]; b[a[i]] = 1; }
int q;
cin >> q;
for (int i = 0; i < q; ++i) {
int k, cnt = 0;
cin >> k;
if (k >= MAX) { cout << 0 << '\n'; continue; }
for (int j = 0; j < n; ++j) { cnt += b[a[j] + k]; }
cout << cnt << '\n';
}
}
Саша Евсиков
Саша Евсиков
76 053
Димка Друг Спасибо
Ну ты спросил.. )
Ищи самый быстрый метод сортировки. Последний раз модифицировал пузырьковый метод лет 20 назад. Вроде быстрые методы на хэшах есть.
И что это за задача - уложиться в секунду.. На какой частоте проца? На скольки ядрах? А то ведь можно поделить задачу на потоки и все.
ДВ
Дмитрий Волков
89 866
Димка Друг Спасибо

Похожие вопросы