Я помню историю, как один товарищ парсил сайт знакомств. Дело в том, что сайт выдавал только некоторую часть информации по каждому объекту. Поэтому товарищ автоматически регил несколько клонов до тех пор, пока не получал всю информацию. Ну, потом все это в базу данных и сортировка по нужному компаратору. Насколько я помню, он нашел что искал.
В этом году требования были. Документ такой на 29 страниц. В прошлых годах, наверняка, тоже были, только я лично их не видел (а может видел, но не помню видел ли).
В 2012 формулировка: собирать на электронные носители, но вместо них можно использовать тестирующую систему. В 2015 же тестирующая система обязательна.
Ну не знаю как было в вашем регионе, у нас лет 5 как участники отправляли решения на сервер через проверяющую систему и она возвращала результат тестирования на тестах из условия (что там было на полных тестах — участникам до конца тура не было известно; первые годы решения проверялись на нашей собственной системе после тура, потом мы прикрутили тестирование на полных тестах параллельно ходу тура, чтобы быстрее получить итоговые результаты, а в 2014 переехали на ejudge с тем же функционалом).
На вики я ничего не трогал, более того — там на текущий момент вроде ничего не изменилось.
А надо было?
На русской вики дан «рецепт» (делайте так-то и так-то и получите то-то), а в английской — некоторые теоретические выкладки почему оно работает (хотя сам алгоритм почему-то толком не описан).
любой алгоритм, решающий задачу сортировки быстрее, чем за O(NlogN) операций, не может работать правильно
в глаза бросилась. Это утверждение справедливо только когда мы не знаем дополнительной информации об элементах и умеем только их попарно сравнивать и обменивать. Товарищ Informatik уже исправился.
я подразумеваю под элементами — сами сортируемые данные, без отношения к списку.
то есть сам список — контейнер для элементов, является цепочкой вершин, внутри которых находятся элементы. как-то так.
я мог кое-где ошибиться в обозначениях, ибо четкой терминологии заранее не строил.
но, думаю, мы поняли друг друга верно)
Если бы к этой статье был бы еще бесплатный доступ… Или я не туда нажимал?
Пока сути алгоритма я совсем не понял, но сразу пару вопросов: корректно ли он ловит случаи, когда элементов равных pivot несколько? и еще когда первый или третий блок после разделения оказываются пустыми?
хм… замечание-то дельное, перечитал референс по std::list, по сути там можно сортить только так:
some_list.sort();
сортировка заточена под список, она перекидывает указатели, указатели остаются валидны.
я же подразумевал вариант вроде этого, где вместо some_list, в принципе, может быть другой контейнер
sort( some_list.begin(), some_list.end() );
но для list оно что-то даже не компилируется:(
Никогда не храните указатели на элементы внутри контейнеров. Мало ли как оно потом будет само себя модифицировать. Первая же реаллокация того же вектора инвалидирует все все ваши указатели.
Фраза «и на списках в том числе» означает, что я могу запустить свою сортировку не только на списке, но и на массиве, и на векторе и на фиг знает еще какой структуре данных, которая предоставляет мне нужный для этого интерфейс, в котором перевешивание указателей не предусмотрено.
надо ставить режим «максимальная производительность»
Вот что я нагуглил: 2012 год, 2015 год.
В 2012 формулировка: собирать на электронные носители, но вместо них можно использовать тестирующую систему. В 2015 же тестирующая система обязательна.
да и авторские решение более чем с запасом укладывались в 0.5 с
поэтому не меняли
А надо было?
На русской вики дан «рецепт» (делайте так-то и так-то и получите то-то), а в английской — некоторые теоретические выкладки почему оно работает (хотя сам алгоритм почему-то толком не описан).
в глаза бросилась. Это утверждение справедливо только когда мы не знаем дополнительной информации об элементах и умеем только их попарно сравнивать и обменивать. Товарищ Informatik уже исправился.
то есть сам список — контейнер для элементов, является цепочкой вершин, внутри которых находятся элементы. как-то так.
я мог кое-где ошибиться в обозначениях, ибо четкой терминологии заранее не строил.
но, думаю, мы поняли друг друга верно)
Пока сути алгоритма я совсем не понял, но сразу пару вопросов: корректно ли он ловит случаи, когда элементов равных pivot несколько? и еще когда первый или третий блок после разделения оказываются пустыми?
some_list.sort();
сортировка заточена под список, она перекидывает указатели, указатели остаются валидны.
я же подразумевал вариант вроде этого, где вместо some_list, в принципе, может быть другой контейнер
sort( some_list.begin(), some_list.end() );
но для list оно что-то даже не компилируется:(
Фраза «и на списках в том числе» означает, что я могу запустить свою сортировку не только на списке, но и на массиве, и на векторе и на фиг знает еще какой структуре данных, которая предоставляет мне нужный для этого интерфейс, в котором перевешивание указателей не предусмотрено.