Вот интересная задача. Объективно простая, но с подвохом.
http://acmp.ru/index.asp?main=task&id_task=822

>>1238
Google / Яндекс

Полагаю, эти омеги были разобраны еще щеночками

>>1965
Зачем нужно лишнее выделение памяти, если отсортировать будет быстрее? Сет это внутри вовсе красно-чёрное дерево вроде как - у него не очень хорошая константа.
Есть сортировка за линейное время, но там тоже константа такая, что n*log(n) быстрее на всём 2≤N≤200000.
10^9 это не так уж и много... ещё есть одно решение за линейное время требующие 1 гб памяти.

>Если все числа в последовательности различны
Помимо этого достаточно найти одну коллизию, и выйти. Логичнее всего прерывать сортировку при нахождении хотя бы одной - нет нужды сортировать или закидывать в set полностью.

>>1247
Участвовал во всеросе когда-то. Не знаю насчёт успехов, два этапа прошёл, а на третий региональный не поехал, потому что мне это было не интересно и я не смотрел даты, а преподаватель смог мне сообщить куда нужно приехать лишь за два часа до начала (потому что я не использовал мобильник) и я уже физически туда никак не успевал. Не очень то и хотелось, правда.

>>1243
>Применяем формулу Герона
Говно ебаное с корнем тормозным, кстати.
Вот картинка, очень простая формула для площади треугольника с углом в начале координат. Причём, у этой площади есть знак. Достаточно сложить площади трёх таких "двуугольников", где вершинами выбирать циклически AB, BC и CA. И модуль от этого взять. Там это ещё как-то в одну формулу сворачивается.

>>2663
Я уже предлагал: >>1966
>Какие подводные у этого способа?
Давай проверим, а то лень душит тред, что всем впадлу 50 строчек написать.
Мне кажется тем, что он упирается в память. Один хочет set создавать, другой массив на гигабайт. Ненормальные.

У меня вот получилось (по вертикали время выполнения, по горизонтали размер данных). И я прав, подход с сортировкой самый быстрый. Даже если в test_4 дописать копирование массив в новый через std::vector<int> brr(arr.begin(),arr.end()) чтобы было честно - всё-равно ничего не меняется.
Массив чисел (рыжим) работает на всех значениях до 200000 наиболее медленно из всех алгоритмов, массив битов(жёлтым; std::vector<bool> же вроде как в виде битсета специализируется?) работает лучше и опережает преобразование в std::set(зелёным) только на значениях больше 12000, а сортировка(розовым) работает за примерно такое же O(nlogn) как и std::set, но с в 12 раз лучшей константой опережая все остальные подходы на всём диапазоне 2≤N≤200000.
Код плюсовый, который в консоль выводит питонокод: https://pastebin.com/DR0u4fiS
Код питонный, где в начале нужно заменить выход плюсового кода, и который выводит график: https://pastebin.com/f03epuKa

Забыл ещё unordered_set (называется hash), который за константу работает.

Ну и вот графики для большего диапазона чисел.

Ещё несколько гибридных подходов прикрутил, но без сложных сложностей - они тоже на десять строк, получилось что-то среднее между массивом на миллиард элементов и обычным алгоритмом с сортировкой.
Битовые поля быстрее всех выше миллиона чисел. Самый тупой код самый быстрый, лол.
Так и не понял как этот чёртов radix написать правильно - хорошо хоть обычный std::sort обогнал, собственно на >20000 элементов он уже стабильно быстрее std::sort - довольно странно что такой алгоритм не содержится в стандартной библиотеке.

>>2665
Я же сделал массив бит тоже специально и он как раз примерно в 8 раз быстрее получился, чем массив на гигабайт из чаров.
Предположил, что доступ к элементу битового массива через сдвиги будет ещё хуже массива байт - но с этим ошибся.

>>2672
Помучил кстати ещё радикс, и добился того, что он работает со скоростью близкой к std::vector<bool>, причём без использования дополнительной памяти.

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