Добавил в тренировки VI Открытая олимпиада школьников по программированию, заочный этап. Специально засек — с момента открытия страницы с тестами и условиями в браузере до финальной публикации контеста прошло 17 минут :)
Почему-то организаторы не публикуют авторские решения. По этой причине тренировка добавлена без капитальной проверки тестов и т.п. Может организаторы опубликуют решения? А еще лучше выложат архив контеста прям из Полигона (вроде бы контест создавался там).
Если кто-то из участников засабмитит свои решения в дорешивание этого контеста, будет отлично — так проверим ограничения времени/памяти и отсутствие разных багов при импорте.
Еще один вопрос к участникам — как вы оцениваете сложность контеста по шкале 5 звезд? Описание можно посмотреть в тренировках (тултипы на звездах существующих тренировок).
Отослал то, что прошло на 100 — вроде отработало нормально.
Повторил этот подвиг. В задаче "Уравнение" получаю ТЛ 24 за 100-балльное решение(если тесты те же, то на 24ом тесте было 0.327). Тестер неправ. :)
У меня такое на задаче G (прямоугольники), работает более, чем в 5 раз медленнее, получает TL.
Аналогично.
Нормальное решение писал? Я-то просто написал хоть и n*log(n), но с большой константой — считывал очередной прямоугольник и пересекал его за логарифм с пересечением предыдущих (строил на углах декартово дерево со всеми вытекающими отсюда последствиями)
Да уж. Декартово дерево + делать всё в онлайне вместо простого scanline? Месье знает толк в извращениях :)
Не знаю почему я не придумал сканлайн, хотя и подозревал, что тут должно быть что-то совсем простое. А кода получилось не так уж много — около 130 строчек :)
Нормальное. UPD : видимо это из-за того, что я cinom читал
Запустил локально. Работает 2 секунды. Так что TL получает правильно. Повторю предположение о странностях в официальном тестировании.
В данном случае такие тормоза от чтения через cin. Заменил на scanf в вашем решении, ускорилось как раз в 5 раз. Так что здесь все чисто.
В задаче "Уравнение" у меня TL24 за 100-бальное решение, хотя на 24-ом тесте было 0,018с и это максимум среди всех 78 тестов.
Я запустил ваше решение локально и оно в самом деле работает долго. Маловероятно, что различия в компиляторе/платформе могли так повлиять на время исполнения. Возможно, это свидетельствует, что на официальном тестировании олимпиады время учитывалось как-то странно.
Локально запустил у себя. Оно у меня работает очень быстро.
Очень странно.
UPD: Ох, надо навести порядок в папках. Я не то решение отправил. Сейчас отправлю нормальное.
UPD2: Всё нормально. Только странно, что здесь зашло за 110 мс, хотя там зашло за 18 мс.
Я запустил ваше решение локально, оно работает 17 секунд. Учитывая мой комментарий ниже, полагаю, что тестирование на официальном туре было некорректное или вы посылали на олимпиаде другую программу.
Там в какой-то момент по задаче "I" добавили тестов и сделали реджадж. Моё решение, например, тогда упало. Вчера послал — 80 мс.
UPD: послал решение, которое тогда потом прошло на сотню
Я взял тесты с olympiads.ru, уж что там не знаю. Возможно да, они что-то нашаманили с тестами.
Не было бы проблем, но посылал именно эту :) Научился оптимизировать до 3.5 секунд (локально), но ТЛ не преодолел. Скоро ещё что-нибудь придумаю.
На мой взгляд, сложность — 4 звезды. Там точно есть неочевидные задачи.
Хоть и не участник, но считаю, что это 4 звезды. Вполне сопоставимо по уровню с крепким div.1 контестом.
Авторское решение J получает AC.