10 октября в 11:00 MSD состоится очередной этап Открытого кубка. Всем удачи!
№ | Пользователь | Рейтинг |
---|---|---|
1 | tourist | 3993 |
2 | jiangly | 3743 |
3 | orzdevinwang | 3707 |
4 | Radewoosh | 3627 |
5 | jqdai0815 | 3620 |
6 | Benq | 3564 |
7 | Kevin114514 | 3443 |
8 | ksun48 | 3434 |
9 | Rewinding | 3397 |
10 | Um_nik | 3396 |
Страны | Города | Организации | Всё → |
№ | Пользователь | Вклад |
---|---|---|
1 | cry | 167 |
2 | Um_nik | 163 |
3 | maomao90 | 162 |
3 | atcoder_official | 162 |
5 | adamant | 159 |
6 | -is-this-fft- | 158 |
7 | awoo | 155 |
8 | TheScrasse | 154 |
9 | Dominater069 | 153 |
10 | nor | 152 |
Название |
---|
Ну это-то понятно, что запрещало сделать 10^4 тестов, вот поэтому и TL. Ты же с увы много пишешь, там такое вообще вроде бы чуть не в каждой задаче :)
Да и с выводом - боян же. cout тормозной, printf непереносимый. Мы сразу ручной вывод int64 писали в тех задачах, где боялись за TL.
Правда, непонятно, зачем тесткейсы давать на не-"Yes"/"No" задачи.
Вот в олимпиадах школьников например - да, такой подход оправдан. Но речь сейчас ведь об ICPC.
ИМХО, объяснение гораздо проще.
Исторически, программы для тестирования, использовавшиеся (да и сейчас кое-где использующиеся) на финала и некоторых полуфиналах ICPC, насколько я знаю, попросту не поддерживали не тесткейсовое тестирование. Например, если посмотреть хотя бы на UVa, то там выдается просто "Wrong Answer" без указания номера теста, так что можно предположить, что по крайней мере изначально примерно так же все было и там.
Более того, подозреваю, что прогон тестов по одному - российское изобретение. PCMS2 - выводит номер теста, на котором упало, Timus и SGU - выводят.
Соответственно, если сказано, что есть t≤1000 тестов, то проверить решение на различных тестах с t=1000 можно и нужно.
Да и безо всяких мультитестов, если сказано 1≤n≤1000, то в тестах жюри обязательно должны присутствовать тесты и с n=1, и с n=1000.
Другое дело, когда ограничение на количество тестов не указано. Для меня это чаще всего означает, что имеется в виду проверка в стиле западных контестов ACM ICPC, и ожидаемое количество тестов по умолчанию — “сотни, но не тысячи”, а сами индивидуальные тесты во вводе не подбираются специально для TL, а образуют как можно более полный тестовый набор.
В последнем случае используется “развитая система умолчаний”, что, на мой взгляд, не очень хорошо — например, потому, что молодые участники могут ниоткуда не знать про эти “сотни, но не тысячи”, и это ставит команды в неравные условия. Чтобы такая проверка была честной, это умолчание должно быть легко найти в правилах конкретного контеста.
Для снарковского сервера это не так. Но какой компилятор на сервере, как там выводить long long, насколько быстро работает cout и какие ограничения в задаче - вроде как не является большим секретом, а тест - противоречащим условию.
Мне не нравится сама идея такого теста, даже если он не был сделан умышленно против cout'а. Ну не для этого тесткейсы нужны, имхо :) К тому же команды привыкнут к таким вот "приколам", а потом на финале будут тратить дополнительное время на защиту от них - и сольют очередным китайцам.
Наверное, предполагалось, что должны были проходить только решения за O(n).
Но ограничения для этого очень маленькими оказались.
"Только О(n) решения" не предпологалось.
сами мы ее решили за NlogN с помощью метода разделяй и властвуй.
UPD. оказывается ниже уже описано такое решение, вопрос снимается:)
Чего-чего? :-D
Что такое обратный ним - в поддавки? И как именно оно сводится? И как влияет то, что мы может только до n/2 брать?
Нет, всё же уточню :)
Решение прямо такое:
0) сгенерировать в a_i всю прогрессию как в int64
1) взять все a_i по модулю n/2 + 1 (обычный модуль - который возвращает от 0 до n/2)
2) если все числа <=1, то если единичек четное число - вывести 1, иначе 0
3) иначе проксорить все числа и вывести это
Неужели точно так же?
EDIT: у нас была бага в чтении d (которое тоже бывает 64битным), при исправлении на long long зашло.
Сохраним в массиве А[1..2*z] количество пар остановок, с каждым возможным расстоянием d. Посчитаем массив sum[0..2*z], в i-ом элементе которого будет сумма элементов массива А с первого до i-го. Ответ на запрос будет таким: sum[r]-sum[l-1].
Мог бы и сам найти, просто залогинившись в контест (посмотрев id у standing'ов ;))
Хоть и не Илья, но расскажу наше решение :)
sqrt-декомпозицией разобьём всё на sqrt(n) блоков.
В каждом блоке будем хранить maximum_x - наибольшее x, которым мы красили весь этот блок, и ещё все числа этого блока в порядке сортировки.
Тогда если поступает запрос присвоения, то во всех блоках, которые попадают в наш отрезок целиком, просто обновляем maximum_x. В двух граничных блоках проходимся и присваиваем значения втупую (за sqrt(n). это можно сделать, не пересорчивая содержимое блока (слиянием за линию двух отсортированных массивов), иначе TL).
Теперь пусть пришёл запрос поиска суммы. В двух граничных блоках ответим на запрос втупую. Теперь что делать с целыми блоками: в каждом таком блоке нужно найти, сколько элементов <= текущего maximum_x этого блока; для этого очевидное решение - сделать бинпоиск по содержимому блока (как раз для этого мы и поддерживали его содержимое в отсортированном порядке), но это будет лишний log в асимптотике. Поэтому, заметив, что maximum_x всегда только возрастает, будет хранить в каждом блоке указатель на первый элемент, >= maximum_x, и продвигать его вправо когда надо.
В сумме должно быть N sqrt(N), а не сдали из-за реализационных косяков.