AT_s8pc_4_h.Huge Kingdom: Atcoder

本题为马拉松题。出题者的解法并不一定能获得满分，请尽量取得更高的得分。
配分：$1500$ 分。

Atcoder 王国由 $N$ 个城市和 $N-1$ 条道路组成。
此外，该王国是连通的。也就是说，是一棵树。

你需要猜出王国的结构。
这里的结构指的是每条道路连接了编号为哪两个城市。

你可以按照如下方式进行询问以推断该结构：

• 输出一个长度为 $N$ 的字符串 $S$。当 $S_i=1$ 时，第 $i$ 个城市被涂黑；当 $S_i=0$ 时，第 $i$ 个城市被涂白。
• 考虑 $N$ 个顶点的图 $G$。
• 如果某条道路两端的城市都被涂黑，则在图 $G$ 中添加该边。
• 返回 $G$ 的每个连通分量的「树的直径」的平方的总和。

例如，若结构如图所示，且 $S=\text{"11001111"}$，则返回的值如下图所示。

在尽量少的询问次数下，推断出王国的结构。

本题为交互题。
最开始，会输入如下内容：

$N$

• 一行，给出 Atcoder 王国的城市数 $N$。

接下来，你可以按如下格式进行询问：

? $S$

$S$ 为你要查询的字符串（即城市涂色方案），长度必须为 $N$。

每次询问后，会返回如下内容：

$d$

按照题目描述的方法构建图 $G$，返回 $G$ 的每个连通分量的「树的直径」的平方的总和。

最后，你需按如下格式输出答案：

! $(a_1,b_1)$ $(a_2,b_2)$ $(a_3,b_3)$ … $(a_{N-1},b_{N-1})$

表示你已推断出 Atcoder 王国的结构。
$(a_i, b_i)$ 表示城市 $a_i$ 与城市 $b_i$ 直接相连。

注意，道路的输出顺序、每条道路 $(a_i, b_i)$ 或 $(b_i, a_i)$ 的顺序均可任选。

限制

• $N = 200$
• Atcoder 王国有 $N-1$ 条道路，且是连通的
• 城市编号为 $0$ 到 $N-1$（从 $0$ 开始编号）
• 测试用例为随机生成

测试用例生成方法

重复以下操作，直到所有城市都连通（只有一个连通分量）为止：

• 随机选择城市编号 $u$ 和 $v$。
• 如果当前状态下，城市 $u$ 和 $v$ 不能通过一些道路相互到达，则在 $u$ 和 $v$ 之间连一条道路。
• 否则，不做任何操作，重新开始。

得分

假设你总共询问了 $L$ 次，理论得分如下：

• 当 $L > 20000$ 时，得分为 $0$
• $L = 18000$ 时，得分为 $500$
• $L = 4000$ 时，得分为 $2000$
• $L = 1200$ 时，得分为 $700$
• 当 $L \leq 700$ 时，得分为 $1500$

共 $5$ 个测试用例，总分为理论值除以 $5$。

样例说明 1

本例中，$N=4$。实际用例中不会出现如此规模（因为不满足限制）。以下为一次互动过程示例。

程序输入
程序输出
4
? 1111
4
? 1101
4
? 1001
0
? 1100
1
? 1011
0
! (0,1) (1,2) (1,3)

王国结构如下图。

注意，未必每次询问都有意义。
此外，未必每次询问都能确认盘面，也可以“猜”答案。

由 ChatGPT 5 翻译