Anya's Simultaneous Exhibition

题意翻译

IO 交互题。 有 $n$ 个人下棋，他们两两之间对战的胜负是确定的，但你不知道。注意，胜负不具有传递性。 你可以进行至多 $2n$ 次询问，询问形式为 `? i s`，其中 $1\le i\le n$，$s$ 是一个长度为 $n$ 的 01 串，$s_j=1$ 表示选择第 $j$ 个人。系统会返回一个值 $x$，表示若 $i$ 与所有被选择的人对战胜利场数。 现在要进行 $n-1$ 场淘汰赛，若你能安排每场比赛的对决双方，问哪些人最终可能留下。

题目描述

This is an interactive problem. Anya has gathered $ n $ chess experts numbered from $ 1 $ to $ n $ for which the following properties hold: - For any pair of players one of the players wins every game against the other (and no draws ever occur); - Transitivity does not necessarily hold — it might happen that $ A $ always beats $ B $ , $ B $ always beats $ C $ and $ C $ always beats $ A $ . Anya does not know, for each pair, who is the player who beats the other.To organize a tournament, Anya hosts $ n-1 $ games. In each game, she chooses two players. One of them wins and stays, while the other one is disqualified. After all the games are hosted only one player will remain. A player is said to be a candidate master if they can win a tournament (notice that the winner of a tournament may depend on the players selected by Anya in the $ n-1 $ games). Since Anya is a curious girl, she is interested in finding the candidate masters. Unfortunately, she does not have much time. To speed up the process, she will organize up to $ 2n $ simuls (short for "simultaneous exhibition", in which one player plays against many). In one simul, Anya chooses exactly one player who will play against some (at least one) of the other players. The chosen player wins all games they would win in a regular game, and the same holds for losses. After the simul finishes, Anya is only told the total number of games won by the chosen player (but not which ones). Nobody is disqualified during a simul. Can you help Anya host simuls and determine the candidate masters? The winning players in each pair could be changed between the simuls, but only in a way that preserves the results of all previous simuls. These changes may depend on your queries.

输入输出格式

输入格式

输出格式

Firstly, the jury sends one integer $ n $ ( $ 3 \leq n \leq 250 $ ) which should be read — the number of players. After that, your program may ask queries or report an answer. To ask a query, print "? $ i \; s_1 s_2 \ldots s_n $ " (without quotes), where $ i $ is the index of the player who will play against some of the other players in the simul. $ s $ is a binary string that denotes the players they play against. $ i $ plays against every player $ j $ for which $ s_j = 1 $ holds (and $ s_j = 1 $ should hold for at least one $ 1 \leq j \leq n $ ). Please note that $ s_i = 0 $ must hold since a player cannot play against themselves, otherwise, the query is considered to be incorrect. After this, you should read an integer — the number of games player $ i $ has won. When you have identified the answer, you must print "! $ c_1 c_2 \ldots c_n $ " (without quotes) and terminate your program. $ c $ is a binary string which represents the candidate masters. Player $ i $ is a candidate master if $ c_i=1 $ holds, otherwise, they are not. If you ask more than $ 2n $ queries or if one of the queries is malformed, the interaction terminates immediately and your program receives verdict Wrong Answer. After printing a query do not forget to output the end of line and flush the output. Otherwise, you will get Idleness limit exceeded. To do this, use: - fflush(stdout) or cout.flush() in C++; - System.out.flush() in Java; - flush(output) in Pascal; - stdout.flush() in Python; - see the documentation for other languages. Hacks are disabled in this problem.

输入输出样例

输入样例 #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

说明

In the first example, the first query describes a simul in which player $ 1 $ plays against player $ 2 $ (and no one else). The answer to the query is $ 1 $ , meaning that player $ 1 $ won the only game they played. We can conclude that $ 1 $ beats $ 2 $ . Similarly, the second query tells us that $ 2 $ beats $ 3 $ and the third query tells us that $ 3 $ beats $ 1 $ . All players are candidate masters in this case as - Player $ 1 $ can win the tournament if $ 2 $ and $ 3 $ play first. $ 3 $ loses and leaves, while $ 2 $ stays. $ 1 $ then plays against $ 2 $ and wins; - Other players can win in the same fashion. In the second example, the third query describes a simul in which player $ 1 $ plays against every other player. The answer to the query is $ 4 $ , meaning that they won every game they played. It can be concluded that player $ 1 $ also beats every other player. They can never lose, hence they are the only player who can remain at the end of every possible tournament, and the only possible candidate master.

**题目大意：**

这是一个交互式问题。有 $ n $ 个棋手，编号从 1 到 $ n $，满足以下条件：

- 对于任意两个棋手，一个棋手总是能赢另一个棋手（永远不会出现平局）；
- 胜利的传递性不一定成立，可能出现 $ A $ 总是赢 $ B $，$ B $ 总是赢 $ C $，而 $ C $ 总是赢 $ A $ 的情况。

组织者 Anya 举行 $ n-1 $ 场淘汰赛。在每场比赛中，她选择两名棋手，赢的棋手留下，输的棋手被淘汰。最后只有一名棋手留下。如果一名棋手能赢得比赛，则称为候选大师。

为了快速找出候选大师，Anya 将组织最多 $ 2n $ 场模拟赛（简写为 "simul"，即 "simultaneous exhibition"，一个棋手同时对战多个棋手）。

在一次模拟赛中，Anya 选择一个棋手对战其他一些（至少一个）棋手。被选中的棋手会赢得他们在正常比赛中会赢的所有比赛，输掉的比赛也同样如此。模拟赛结束后，Anya 只被告知被选中的棋手赢得的比赛总数（但不知道具体是哪些比赛）。在模拟赛中没有人会被淘汰。

你需要帮助 Anya 通过模拟赛找出候选大师。

每对棋手中赢的棋手在模拟赛之间可能会改变，但必须保持所有先前模拟赛的结果。这些变化可能取决于你的查询。

**输入输出格式：**

**输入格式：**
首先裁判发送一个整数 $ n $（$ 3 \leq n \leq 250 $），表示棋手的数量。之后你的程序可以提出查询或报告答案。

为了提出查询，打印 "? $ i \; s_1 s_2 \ldots s_n $"（不带引号），其中 $ i $ 是将对战其他一些棋手的棋手的索引。$ s $ 是一个二进制字符串，表示他们将对抗的棋手。$ i $ 将与每个 $ s_j = 1 $ 的棋手 $ j $ 对战（至少有一个 $ 1 \leq j \leq n $ 的 $ s_j = 1 $）。请注意 $ s_i = 0 $ 必须成立，因为一个棋手不能与自己对战，否则查询被认为是错误的。

在此之后，你应该读取一个整数——棋手 $ i $ 获胜的游戏数。

当你确定答案时，你必须打印 "! $ c_1 c_2 \ldots c_n $" 并终止你的程序。$ c $ 是一个二进制字符串，代表候选大师。如果 $ c_i=1 $ 成立，则棋手 $ i $ 是候选大师，否则他们不是。

如果你提出超过 $ 2n $ 个查询，或者其中一个查询格式错误，交互将立即终止，你的程序将得到错误的答案。

在打印查询后不要忘记输出换行符并刷新输出。否则，你将得到空闲时间限制超出的错误。具体刷新输出的方法取决于使用的编程语言。

**输出格式：**
请参照输入输出样例。**题目大意：** 这是一个交互式问题。有 $ n $ 个棋手，编号从 1 到 $ n $，满足以下条件： - 对于任意两个棋手，一个棋手总是能赢另一个棋手（永远不会出现平局）； - 胜利的传递性不一定成立，可能出现 $ A $ 总是赢 $ B $，$ B $ 总是赢 $ C $，而 $ C $ 总是赢 $ A $ 的情况。 组织者 Anya 举行 $ n-1 $ 场淘汰赛。在每场比赛中，她选择两名棋手，赢的棋手留下，输的棋手被淘汰。最后只有一名棋手留下。如果一名棋手能赢得比赛，则称为候选大师。 为了快速找出候选大师，Anya 将组织最多 $ 2n $ 场模拟赛（简写为 "simul"，即 "simultaneous exhibition"，一个棋手同时对战多个棋手）。 在一次模拟赛中，Anya 选择一个棋手对战其他一些（至少一个）棋手。被选中的棋手会赢得他们在正常比赛中会赢的所有比赛，输掉的比赛也同样如此。模拟赛结束后，Anya 只被告知被选中的棋手赢得的比赛总数（但不知道具体是哪些比赛）。在模拟赛中没有人会被淘汰。 你需要帮助 Anya 通过模拟赛找出候选大师。 每对棋手中赢的棋手在模拟赛之间可能会改变，但必须保持所有先前模拟赛的结果。这些变化可能取决于你的查询。 **输入输出格式：** **输入格式：** 首先裁判发送一个整数 $ n $（$ 3 \leq n \leq 250 $），表示棋手的数量。之后你的程序可以提出查询或报告答案。 为了提出查询，打印 "? $ i \; s_1 s_2 \ldots s_n $"（不带引号），其中 $ i $ 是将对战其他一些棋手的棋手的索引。$ s $ 是一个二进制字符串，表示他们将对抗的棋手。$ i $ 将与每个 $ s_j = 1 $ 的棋手 $ j $ 对战（至少有一个 $ 1 \leq j \leq n $ 的 $ s_j = 1 $）。请注意 $ s_i = 0 $ 必须成立，因为一个棋手不能与自己对战，否则查询被认为是错误的。 在此之后，你应该读取一个整数——棋手 $ i $ 获胜的游戏数。 当你确定答案时，你必须打印 "! $ c_1 c_2 \ldots c_n $" 并终止你的程序。$ c $ 是一个二进制字符串，代表候选大师。如果 $ c_i=1 $ 成立，则棋手 $ i $ 是候选大师，否则他们不是。 如果你提出超过 $ 2n $ 个查询，或者其中一个查询格式错误，交互将立即终止，你的程序将得到错误的答案。 在打印查询后不要忘记输出换行符并刷新输出。否则，你将得到空闲时间限制超出的错误。具体刷新输出的方法取决于使用的编程语言。 **输出格式：** 请参照输入输出样例。