哈密顿 - Problem

考虑一个包含 $n$ 个节点（编号为 $1, 2, \dots, n$）的有向图。如果图中任意一对节点之间都恰好有一条有向边，则称该图为竞赛图（tournament）。也就是说，对于任意两个不同的节点 $u$ 和 $v$，要么存在从 $u$ 到 $v$ 的边，要么存在从 $v$ 到 $u$ 的边。

哈密顿回路是一个访问所有节点并回到起点的序列 $c_1, c_2, \dots, c_n$，且该序列沿图中的边行进。对于所有 $1 \le i \le n - 1$，必须存在从 $c_i$ 到 $c_{i+1}$ 的边。此外，还必须存在从 $c_n$ 到 $c_1$ 的边。

你可以自由构造一个包含 $n$ 个节点的竞赛图。随后，节点的编号会被打乱。通过对打乱后的图进行关于边方向的询问，你能否找到一条哈密顿回路？

这是一个交互式问题。首先读取两个整数 $n$ 和 $t$：节点数量和测试用例数量。

接下来，输出 $n$ 行来描述你构造的竞赛图。在第 $u$ 行中，输出 $n$ 个字符 "0" 或 "1"。位置 $v$ 处的字符 "1" 表示存在一条从 $u$ 到 $v$ 的边。不应存在从 $u$ 到 $u$ 的边。

随后进行 $t$ 个测试用例。每个测试用例使用你提供的同一个图，但节点编号已被打乱，且对你保密。你可以进行若干次询问，之后你需要报告一条哈密顿回路。

进行询问时，输出 ? u v，其中 $1 \le u, v \le n$ 是打乱后图中的不同节点。评测机将返回 ">"（表示存在从 $u$ 到 $v$ 的边）或 "<"（表示存在从 $v$ 到 $u$ 的边）。

当你找到一条哈密顿回路后，输出 "!"，后跟 $n$ 个整数 $c_1, c_2, \dots, c_n$。注意，数字 $c_i$ 应遵循打乱后的编号。在你输出答案后，下一个测试用例立即开始。

你可以从这里下载测试脚本。脚本开头包含使用说明。

5 2
01110
00101
00010
01001
10100
? 1 2
>
? 2 3
>
? 3 4
>
? 4 5
>
? 5 1
>
! 1 2 3 4 5
? 1 2
<
? 1 5
>
? 4 3
>
? 4 5
<
? 3 2
>
! 1 5 4 3 2

(交互过程见输入格式)

在第一个测试用例中，节点恰好被打乱为原始顺序，因此 $1, 2, 3, 4, 5$ 是一条哈密顿回路。

在第二个测试用例中，节点编号被打乱为 $2, 4, 1, 5, 3$。序列 $1, 5, 4, 3, 2$ 确实是一条哈密顿回路，因为 $3, 4, 2, 5, 1$ 在原始图中是一条边序列。

下图左侧展示了原始图，右侧展示了第二个测试用例中打乱后的图。两条哈密顿回路均以红色高亮显示。

原始图（左）与打乱后的图（右）

每个子任务包含一个测试输入，其中 $t = 200$。在每个测试用例中，图的编号是均匀随机打乱的。在单个测试用例中进行超过 $10^4$ 次询问会导致判决为 WRONG ANSWER。

设 $Q$ 为你的程序在子任务所属的所有测试用例中进行的平均询问次数。如果 $Q$ 不超过指定的限制，你将获得该子任务的分数。

在子任务 4 中，你根据以下公式获得分数：

$$\left\lfloor \frac{25\,000}{\max(750, Q) - 500} - 24 \right\rfloor$$

例如，如果你的程序进行的平均询问次数为 $Q = 1500$，你将获得 1 分；如果 $Q = 1000$，你将获得 26 分；如果 $Q = 750$，你将获得 76 分。

QOJ.ac