← 返回题目列表

Codeforces · 1779/E

E. 安雅同期展

中文机器翻译题面 查看原题

这是一个交互问题。

Anya 聚集了 $$$n$$$ 位国际象棋专家,编号从 $$$1$$$ 到 $$$n$$$,这些专家具有以下属性:

- 对于任何一对玩家,其中一个玩家在与另一个玩家的每场比赛中获胜(并且不会发生平局);
- 传递性不一定成立 - 可能会发生 $$$A$$$ 总是击败 $$$B$$$,$$$B$$$ 总是击败 $$$C$$$ 和 $$$C$$$ 总是击败 $$$A$$$。

为了组织锦标赛,Anya 举办了 $$$n-1$$$ 游戏。在每场比赛中,她都会选择两名球员。其中一名获胜并留下来,而另一名则被取消资格。所有比赛结束后,只剩下一名球员。如果玩家能够赢得锦标赛,则称其为候选大师(请注意,锦标赛的获胜者可能取决于 Anya 在 $$$n-1$$$ 游戏中选择的玩家)。

由于安雅是一个好奇的女孩,她对寻找候选大师很感兴趣。不幸的是,她的时间不多了。为了加快这一过程,她将组织最多$$$2n$$$ simuls(“同时表演”的缩写,其中一名玩家与多名玩家对战)。

在一场模拟中,Anya 恰好选择了一名玩家来与其他一些(至少一名)玩家对战。被选中的玩家赢得了他们在常规比赛中会赢得的所有比赛,同样的情况也适用于输球。同时完成后,安雅只会得知所选玩家获胜的总局数(而不是哪些局数)。在同时进行的比赛中,没有人被取消资格。

你能帮助安雅主持模拟赛并确定候选大师吗?

每对中的获胜玩家可以在模拟之间进行更改,但只能以保留所有先前模拟结果的方式进行更改。这些更改可能取决于您的查询。

互动

首先,陪审团发送一个整数 $$$n$$$ ($$$3 \leq n \leq 250$$$),该整数应该被读取——玩家数量。之后,您的程序可能会提出疑问或报告答案。

要提出查询,请打印“? $$$i \; s_1 s_2 \ldots s_n$$$”(不带引号),其中 $$$i$$$ 是将在模拟中与其他一些玩家对战的玩家的索引。 $$$s$$$ 是一个二进制字符串,表示他们对抗的玩家。 $$$i$$$ 与 $$$s_j = 1$$$ 成立的每个玩家 $$$j$$$ 进行比赛(并且 $$$s_j = 1$$$ 应至少成立一个 $$$1 \leq j \leq n$$$)。请注意,$$$s_i = 0$$$ 必须成立,因为玩家无法与自己对战,否则查询将被视为不正确。

此后,您应该读取一个整数 - 玩家 $$$i$$$ 获胜的人数。

确定答案后,必须打印“! $$$c_1 c_2 \ldots c_n$$$”(不带引号)并终止程序。 $$$c$$$ 是一个二进制字符串,表示候选大师。如果 $$$c_i=1$$$ 成立,则玩家 $$$i$$$ 是候选大师,否则不是。

如果您提出超过 $$$2n$$$ 查询,或者其中一个查询格式错误,则交互会立即终止,并且您的程序会收到错误答案的判决。

打印查询后,不要忘记输出行尾并刷新输出。否则,您将超出空闲限制。为此,请使用:

- C++ 中的 fflush(stdout) 或 cout.flush();
- Java 中的 System.out.flush();
- 帕斯卡刷新(输出);
- Python 中的 stdout.flush() ;
- 请参阅其他语言的文档。

在此问题中,黑客被禁用。

示例

输入 #1

3

1

1

1

输出 #1

? 1 010

? 2 001

? 3 100

! 111

输入 #2

5

0

3

4

输出 #2

? 5 10110

? 2 10111

? 1 01111

! 10000

注意

在第一个示例中,第一个查询描述了一个模拟,其中玩家 $$$1$$$ 与玩家 $$$2$$$(没有其他人)对战。查询的答案是 $$$1$$$,这意味着玩家 $$$1$$$ 赢得了他们玩的唯一一场游戏。我们可以得出结论,$$$1$$$ 击败 $$$2$$$。同样,第二个查询告诉我们 $$$2$$$ 击败 $$$3$$$,第三个查询告诉我们 $$$3$$$ 击败 $$$1$$$。在这种情况下,所有玩家都是候选大师

- 如果 $$$2$$$ 和 $$$3$$$ 先玩,玩家 $$$1$$$ 就可以赢得比赛。 $$$3$$$ 输了并离开,而 $$$2$$$ 留下来。 $$$1$$$ 然后与 $$$2$$$ 比赛并获胜;
- 其他玩家可以以同样的方式获胜。

在第二个示例中,第三个查询描述了玩家 $$$1$$$ 与其他所有玩家对战的模拟。查询的答案是 $$$4$$$,这意味着他们赢得了每场比赛。可以得出结论,玩家 $$$1$$$ 也击败了其他所有玩家。他们永远不会输,因此他们是唯一能够在所有可能的锦标赛结束时留下来的玩家,也是唯一可能的候选大师。