E. Параллельные показательные матчи Ани
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Это интерактивная задача.

Аня собрала $$$n$$$ шахматных экспертов, пронумерованных от $$$1$$$ до $$$n$$$, для которых выполняются следующие свойства:

  • Для любой пары игроков один игрок всегда выигрывает игру против другого (ничей не бывает);
  • Свойство транзитивности не обязательно выполняется: может быть такое, что $$$A$$$ всегда выигрывает $$$B$$$, $$$B$$$ всегда выигрывает $$$C$$$, а $$$C$$$ всегда выигрывает $$$A$$$.
Аня не знает, кто из игроков выигрывает кого в каждой паре.

Рассмотрим турнир из $$$n-1$$$ игр. В каждой игре Аня выбирает двух игроков. Один из них выигрывает и остается в турнире, другой выбывает. После всех игр только остается только один игрок, называемый победителем. Игрок называется кандидатом в мастера, если он может победить в турнире (обратите внимание, что победитель турнира может зависеть от Аниного выбора игроков в $$$n-1$$$ игре).

Так как Аня — любознательная девочка, ей интересно найти, какие игроки являются кандидатами в мастера. К сожалению, у нее не очень много времени. Она может организовать не более $$$2n$$$ сеансов параллельной игры, в которых один игрок играет против многих.

В каждом сеансе Аня выберет ровно одного игрока, который сыграет по одной партии против нескольких (как минимум одного) других игроков. Выбранный игрок выиграет все игры, которые он бы выиграл в обычных условиях, то же самое верно для проигрышей. После окончания сеанса Аня узнает только количество партий, выигранных выбранным игроком (но не какие из партий были выиграны). По результатам сеанса никто не выбывает из турнира.

Можете помочь Ане определить кандидатов в мастера?

Выигрывающий игрок в каждой паре игроков может быть изменен между сеансами, но только так, чтобы результаты всех предыдущих сеансов сохранились. Эти изменения могут зависеть от ваших запросов.

Протокол взаимодействия

Сначала считайте одно целое число $$$n$$$ ($$$3 \leq n \leq 250$$$) — количество игроков. После этого вы можете устраивать сеансы или выводить ответ.

Чтобы устроить сеанс, выведите «? $$$i \; s_1 s_2 \ldots s_n$$$» (без кавычек), где $$$i$$$ — номер игрока, который будет одновременно играть против других. $$$s$$$ — бинарная строка, обозначающая, против кого будет играть этот игрок. $$$i$$$ играет против каждого $$$j$$$, для которого выполняется $$$s_j = 1$$$ ($$$s_j = 1$$$ должно выполняться хотя бы для одного $$$1 \leq j \leq n$$$). Обратите внимание, должно выполняться $$$s_i = 0$$$, так как игрок не может играть сам против себя, иначе запрос считается некорректным.

После этого считайте одно целое число — количество партий, в которых выиграл $$$i$$$.

Когда вы нашли ответ, выведите «! $$$c_1 c_2 \ldots c_n$$$» (без кавычек) и завершите свою программу. $$$c$$$ — бинарная строка, показывающая кандидатов в мастера. Игрок $$$i$$$ является кандидатом в мастера, если выполняется $$$c_i=1$$$, иначе он им не является.

Если вы сделаете более $$$2n$$$ запросов, или какой-то запрос некорректен, взаимодействие немедленно завершится, и вы получите вердикт Неправильны ответ.

После вывода запроса не забудьте вывести перевод строки и сбросить буфер вывода. В противном случае вы получите вердикт Решение «зависло». Для сброса буфера используйте:

  • fflush(stdout) или cout.flush() в C++;
  • System.out.flush() в Java;
  • flush(output) в Pascal;
  • stdout.flush() в Python;
  • смотрите документацию для других языков.

Взломы в этой задаче запрещены.

Примеры
Входные данные
3

1

1

1
Выходные данные

? 1 010

? 2 001

? 3 100

! 111
Входные данные
5

0

3

4
Выходные данные

? 5 10110

? 2 10111

? 1 01111

! 10000
Примечание

В первом примере первый запрос описывает сеанс игрока $$$1$$$ против игрока $$$2$$$ (и никого другого). Ответ на запрос равен $$$1$$$, что означает, что игрок $$$1$$$ выиграл единственную игру. Можно заключить, что $$$1$$$ побеждает $$$2$$$. Аналогично во втором запросе $$$2$$$ побеждает $$$3$$$, и в третьем запросе $$$3$$$ побеждает $$$1$$$. Все игроки являются кандидатами в мастера, потому что

  • Игрок $$$1$$$ может выиграть турнир, если сначала играют $$$2$$$ и $$$3$$$. $$$3$$$ проигрывает и выбывает, а $$$2$$$ остается. $$$1$$$ играет против $$$2$$$ и выигрывает;
  • Другие игроки могут выиграть аналогично.

Во втором примере третий запрос описывает сеанс игрока $$$1$$$ против всех остальных. Ответ на этот запрос равен $$$4$$$, что означает, что им были выиграны все игры. Можно понять, что $$$1$$$ побеждает всех других игроков. Так как этот игрок не может проиграть, то только он может остаться в конце турнира, то есть это единственный кандидат в мастера.