#5716. 「BalticOI 2026」哈密顿

标签: 交互 | 时间限制: 10000 ms | 内存限制: 512 MiB |

题目描述

题目译自 BalticOI 2026 Day2「Hamilton」

考虑一个有 $n$ 个结点的有向图，结点编号为 $1, 2, \ldots, n$。若任意两点之间恰好存在一条有向边，则称该图为竞赛图。也就是说，对于任意两个不同的结点 $u$ 和 $v$，要么存在从 $u$ 到 $v$ 的边，要么存在从 $v$ 到 $u$ 的边。

哈密顿回路是一个序列 $c_{1}, c_{2}, \ldots, c_{n}$，它访问图中所有结点并最终回到起点，且路径必须沿着图中的边进行。对于所有 $1 \leq i \leq n-1$，必须存在从 $c_{i}$ 到 $c_{i+1}$ 的边。此外，必须存在从 $c_{n}$ 到 $c_{1}$ 的边。

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

交互方式

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

接着，输出 $n$ 行来描述竞赛图。在这些行中的第 $u$ 行，输出 $n$ 个字符 0 或 1。位置 $v$ 处的字符 1 表示存在一条从 $u$ 到 $v$ 的边。注意 $u$ 到自身不应有边。

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

进行询问时，输出 ? $u \ v$，其中 $1 \leq u, v \leq n$ 是打乱后图中不同的结点。交互器会回复 > 表示边是从 $u$ 指向 $v$，或者 < 表示边是从 $v$ 指向 $u$。

当你找到哈密顿回路后，输出 !，随后输出 $n$ 个整数 $c_{1}, c_{2}, \ldots, 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$ 是一条哈密顿回路。

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

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

数据范围与提示

对于所有输入数据，满足：

• $4 \leq n \leq 500$
• $1 \leq t \leq 200$

每个子任务中仅有一个测试输入，包含 $t=200$ 个测试用例。在每个测试用例中，图的结点编号是随机均匀打乱的。在单个测试用例中询问次数超过 $10^{4}$ 次将导致结果为 WRONG ANSWER。

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

详细子任务附加限制及分值如下表所示。

子任务	附加限制	分值
$1$	$n=4, Q \leq 12$	$5$
$2$	$n=50, Q \leq 1225$	$7$
$3$	$n=50, Q \leq 300$	$12$
$4$	$n=500, Q \leq 1500$	$1-76$

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

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

若你的程序平均询问次数 $Q=1500$，则该子任务得 $1$ 分。若 $Q=1000$，则得 $26$ 分；若 $Q=750$，则得 $76$ 分。