Codeforces Round 616 (Div. 1) |
---|
Закончено |
Это сложная версия этой задачи. Вы можете найти простую версию в Div. 2 контесте. Обе версии отличаются только в ограничении на количество раз, которое вы можете попросить вашего друга попробовать кофе.
Это интерактивная задача.
Вы собираетесь поехать в другой город, где живет один из ваших друзей. В этом городе $$$n$$$ кафе, где число $$$n$$$ является степенью двойки. В $$$i$$$-м кафе варят кофе сорта $$$a_i$$$.
Поскольку вы большой любитель кофе, перед тем, как выбрать поехать ли в этот город или нет, вы хотите узнать количество различных сортов кофе $$$d$$$, которое варят в этом городе.
Вы не знаете значений $$$a_1, \ldots, a_n$$$. К счастью, ваш друг хорошо запоминает события последних $$$k$$$ дней, где $$$k$$$ это степень двойки.
Каждый день, вы можете попросить его попробовать чашечку кофе, сваренного в кафе с номером $$$c$$$ и он скажет, пробовал ли он кофе того же сорта в последние $$$k$$$ дней.
Также вы можете попросить его забыть все, что он пробовал до этого. После этого он забудет все предыдущие разы, когда он пробовал кофе. Вы можете делать это не больше $$$30\ 000$$$ раз.
Более формально, память вашего друга это некоторая очередь $$$S$$$. Сделать запрос сходить попробовать кофе в кафе с номером $$$c$$$ означает:
Запрос забывания всех посещений кафе удаляет все элементы очереди $$$S$$$, то есть отчищает ее.
Вы можете попросить вашего друга попробовать не больше $$$\dfrac{3n^2}{2k}$$$ чашек кофе. Найдите разнообразность города $$$d$$$ (количество различных значений в массиве $$$a$$$).
Обратите внимание, что попросить вашего друга забыть все походы в кафе, что были до этого не считается среди количества запросов попросить вашего друга попробовать кофе.
В некоторых тестах поведение интерактора будет адаптивным. Это означает, что массив $$$a$$$ может быть не фиксированным до начала тестирования вашей программы и может зависеть от ваших запросов. Гарантируется, что в любой момент тестирования, существует хотя бы один массив $$$a$$$, для которого верны все данные до этого ответы на запросы.
В первой строке находится два целых числа $$$n$$$ и $$$k$$$ ($$$1 \le k \le n \le 1024$$$, $$$k$$$ и $$$n$$$ это степени двойки).
Гарантируется, что $$$\dfrac{3n^2}{2k} \le 15\ 000$$$.
Вы начинаете взаимодействие со считывания двух чисел $$$n$$$ и $$$k$$$.
? $$$c$$$
Тут $$$c$$$ должно удовлетворять условиям $$$1 \le c \le n$$$. Не забывайте сделать сброс буфера потока вывода после этого.
В ответ вы получите символ Y (да) или N (нет), сообщающий вам, встречался ли сорт кофе $$$a_c$$$ среди последних $$$k$$$ сортов кофе в памяти вашего друга.
! $$$d$$$
В случае, если запрос, сделанный вами, некорректный или вы сделали больше, чем $$$\frac{3n^2}{2k}$$$ запросов типа ? или больше, чем $$$30\ 000$$$ запросов типа R, в ответ тестирующая программа выведет символ E и закончит тестирование. Вы получите вердикт Wrong Answer. Будьте осторожны, для этого ваша программа должна немедленно завершиться в этом случае, иначе вердикт посылки может быть любым.
После вывода запроса не забывайте переводить строку и делать сброс буфера потока вывода. Иначе, вы получите вердикт Idleness limit exceeded. Для того, чтобы сделать сброс буфера потока вывода, используйте:
Взломы
В первой строке теста должно находиться слово fixed
Во второй строке должны содержаться два целых числа $$$n$$$ и $$$k$$$, разделенных пробелом ($$$1 \le k \le n \le 1024$$$, $$$k$$$ и $$$n$$$ это степени двойки).
Должно быть выполнено, что $$$\dfrac{3n^2}{2k} \le 15\ 000$$$.
В третьей строке должны содержаться $$$n$$$ целых чисел $$$a_1, a_2, \ldots, a_n$$$, разделенных пробелом ($$$1 \le a_i \le n$$$).
4 2 N N Y N N N N
? 1 ? 2 ? 3 ? 4 R ? 4 ? 1 ? 2 ! 3
8 8 N N N N Y Y
? 2 ? 6 ? 4 ? 5 ? 2 ? 5 ! 6
В первом тесте, массив $$$a = [1, 4, 1, 3]$$$. В городе производится $$$3$$$ различных сорта кофе ($$$1$$$, $$$3$$$ и $$$4$$$).
Последовательные сорта кофе, попробованные вашим другом это $$$1, 4, \textbf{1}, 3, 3, 1, 4$$$ (жирным выделены запросы с ответом Y). Обратите внимание, что между двумя запросами ? 4, был запрос отчищения памяти, поэтому ответ на второй запрос ? 4 был N. Если бы этого запроса не было, то ответ на второй запрос ? 4 был бы Y.
Во втором тесте, массив $$$a = [1, 2, 3, 4, 5, 6, 6, 6]$$$. В городе производится $$$6$$$ различных сортов кофе.
Последовательные сорта кофе, попробованные вашим другом это $$$2, 6, 4, 5, \textbf{2}, \textbf{5}$$$.
Название |
---|