Codeforces Round 889 (Div. 1) |
---|
Закончено |
Майкл и Брайан застряли в отеле с $$$n$$$ номерами, пронумерованными от $$$1$$$ до $$$n$$$, и должны найти друг друга. Но все двери в отеле заперты, и единственный способ передвижения — это использование телепортов в каждом номере. В номере $$$i$$$ есть телепорт, который перенесет вас в номер $$$a_i$$$ (может оказаться, что $$$a_i = i$$$). Но они не знают значений $$$a_1,a_2, \dots, a_n$$$.
Вместо этого они могут позвонить в регистратуру и задать запрос. В одном из запросов они указывают номер $$$u$$$, целое положительное число $$$k$$$ и набор номеров $$$S$$$. Консьерж отеля отвечает, попадет ли человек, начав жить в номере $$$u$$$ и воспользовавшись телепортами $$$k$$$ раз, в номер из набора $$$S$$$.
Брайан находится в номере $$$1$$$. Майкл хочет знать набор номеров $$$A$$$ такой, что если он начнет жить в одном из этих номеров, они могли встретиться с помощью телепортов. Он может задать не более $$$2000$$$ запросов.
Значения $$$a_1, a_2, \dots, a_n$$$ фиксированы до начала взаимодействия и не зависят от запросов. Другими словами, интерактор не является адаптивным.
На вход подается одно целое число $$$n$$$ ($$$2 \leq n \leq 500$$$).
Чтобы сделать запрос, выведите строку в формате «? u k |S| S_1 S_2 ... S_|S|», в которой $$$1 \leq u, S_1, \ldots, S_{|S|} \leq n$$$, все $$$S_i$$$ различны, а $$$1 \leq k \leq 10^9$$$.
В качестве ответа на запрос вы получите «1», если ответ положительный, и «0», если ответ отрицательный.
Чтобы вывести ответ, необходимо напечатать «! |A| A_1 A_2 ... A_|A|», где $$$1 \leq A_1, \ldots, A_{|A|} \leq n$$$, все они различны. Вывод ответа не считается запросом.
Для большей ясности смотрите пример взаимодействия.
Если вы зададите слишком много запросов или неправильно сформируете запрос, то получите вердикт Неправильный ответ.
После вывода запроса не забудьте вывести перевод строки и сбросить буфер вывода. В противном случае вы получите вердикт Решение «зависло». Для сброса буфера используйте:
Взломы
Для взломов используйте следующий формат.
Первая строка должна содержать $$$n$$$ — количество комнат.
Вторая строка должна содержать $$$n$$$ целых чисел $$$a_1, a_2, \dots, a_n$$$ — телепорт в комнате $$$i$$$ ведет в комнату $$$a_i$$$.
5 0 1
? 3 5 2 2 3 ? 2 5 2 2 3 ! 3 1 3 4
В примере имеется $$$n=5$$$ комнат, а массив (скрытый), описывающий поведение телепортов, имеет вид $$$[1, 2, 1, 3, 2]$$$.
Название |
---|