Закончился второй раунд. Интересно, как решать C, F?
| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | Benq | 3676 |
| 2 | Kevin114514 | 3659 |
| 3 | jiangly | 3640 |
| 4 | turmax | 3450 |
| 5 | tourist | 3408 |
| 6 | strapple | 3360 |
| 7 | Um_nik | 3354 |
| 8 | squareOf105 | 3348 |
| 9 | maroonrk | 3312 |
| 10 | idontwannadothis…e | 3191 |
| Страны | Города | Организации | Всё → |
| № | Пользователь | Вклад |
|---|---|---|
| 1 | Qingyu | 153 |
| 2 | nik_exists | 151 |
| 3 | maroonrk | 150 |
| 4 | maspy | 149 |
| 5 | AmShZ | 146 |
| 6 | Um_nik | 143 |
| 7 | Errichto | 139 |
| 8 | adamant | 135 |
| 9 | BledDest | 134 |
| 10 | cry | 130 |
Закончился второй раунд. Интересно, как решать C, F?
| Название |
|---|



Интересно я один пытался запихивать хеши на B ?
Расскажите пожалуйста нормальное решение)
У меня зашло решение в лоб: для каждой клетки-центра креста расширяемся, пока можно, и обновляем ответ.
Обидно)
Я писал бинпоиск + хеши, думал еще как-то Манакера использовать)
Спасибо)
Я успел только прочитать эту задачу, но мне кажется, что можно использовать идею выше, только сравнивать за раз сразу по 32 клетки с помощью преобразований масок в инты. А при неравенстве уже влоб проходить. Итого должно получаться O(N^2 * (N / 32 + 32))
А почему "запихивать"? Оно там вполне нормально заходит, без каких-либо проблем. Памяти на все хватает, по времени — у меня 0.684, запас х10.
Антихештестов тоже нету :)
Upd. Код.
значит я криворукий)
Все время ВА получал
Спасибо:)
Переписал и зашло)
С обходом антихеш тестов у меня 2.9, при этом на случайном макстесте на сервере (в задаче Х) 5 с
F: Для начала посчитаем, какое количество монет может быть перевернуто после выполнения всех действий. Заметим, что если после выполнения некоторых действий может быть перевернуто минимально min и максимально max монет, то может быть перевернуто и произвольное количество монет cnt, такое что min ≤ cnt ≤ max и cnt совпадает по четности с min и max (они всегда совпадают по четности между собой). Поэтому будем просто выполнять последовательно действия и считать эти min и max после каждого действия, зная каковы они были перед выполнением действия. Внутри перехода min и max я считал разбором нескольких случаев, примерно так:
В конце мы знаем, какое количество монет может быть перевернуто, для каждого такого количества cnt прибавляем к ответу число сочетаний из N по cnt.
Полный код (метод solve в самом конце)
А код для to во избежание багов можно не писать, а вызвать код для from с (from, to) --> (m — to, m — from), и взяв m — результат.
Да, вчера вечером я тоже это придумал, но на контесте ограничился "скопировать, просмотреть ошибку, получить WA вслепую" за минуту до конца раунда.