CF2179G Blackslex and Penguin Migration

[IOI 2025 - Migrations](https://oj.uz/problem/view/IOI25_migrations) 本题为交互题。 Blackslex 正在研究的一种企鹅居住在一个 $n$ 行 $n$ 列的岛屿网格上。每个格子里恰好有一只企鹅。 他把每只企鹅编号为 $1$ 到 $n^2$。经过一段时间后，有些企鹅迁移到了其他格子。迁移之后，仍然每只企鹅会在某个格子里，并且每个格子都有且仅有一只企鹅。他现在需要获得每只企鹅的当前位置。 为此，他可以向一只企鹅询问与另一只企鹅的距离。 具体来说，设 $x$ 为某种企鹅在网格中的位置方案，$\operatorname{dist}(x, i, j)$ 表示企鹅 $i$ 与企鹅 $j$ 在 $x$ 网格中的曼哈顿距离 $^{\ast}$。 现在有一个隐藏的网格 $a$，包含 $n$ 行 $n$ 列。你需要找出一个网格 $b$，满足以下条件： - $b$ 是 $n$ 行 $n$ 列的网格。 - 每个格子填入 $1$ 到 $n^2$ 之间的整数，每个编号只出现一次。 - 对所有 $1 \leq i, j \leq n^2$，都有 $\operatorname{dist}(a, i, j) = \operatorname{dist}(b, i, j)$。 你可以进行不超过 $3n^2+150$ 次如下操作： - 给定 $i$，$j$（$1 \leq i, j \leq n^2$），获得 $\operatorname{dist}(a, i, j)$ 的值。 $^{\ast}$ 设 $r_i$，$c_i$ 分别为企鹅 $i$ 所在的行列位置，同理 $r_j$，$c_j$ 表示企鹅 $j$ 的行列，则曼哈顿距离为 $|r_i-r_j|+|c_i-c_j|$。

每个测试点包含多组测试数据。第一行包含整数 $t$（$1 \leq t \leq 200$）——测试数据的组数。 每组数据的第一行包含一个整数 $n$（$2 \leq n \leq 100$）——岛屿的边长。 保证所有测试数据的 $n$ 之和不超过 $500$。

（本题为交互题，无固定输出格式。参见原题交互协议实现。）

注意附加的换行仅供易读，实际输出中不应输出这些内容。 在第一个测试用例中，隐藏网格 $a$ 是 1423 在第二个测试用例中，隐藏网格 $a$ 是 913427856 交互过程示例如下： Contestant Judge Description 2 // 第一组数据开始，岛屿大小为 $n=2$ ? 1 2 // 选手查询企鹅1和2的距离 1 // 企鹅1和2的距离为1 ? 1 3 2 ? 1 4 1 ? 2 3 1 ? 2 4 2 ? 3 4 1 ! // 选手确定了一个可能的网格 $b$ 3 4 注意，所提交的网格不需要与隐藏网格完全一致，但需满足对所有 $1 \leq i, j \leq n^2$，都有 $\operatorname{dist}(a, i, j) = \operatorname{dist}(b, i, j)$。 2 // 第二组数据开始，岛屿大小为 $n=3$ ? 1 8 // 选手查询企鹅1和8的距离 3 ! 9 1 3 4 2 7 8 5 6 由 ChatGPT 5 翻译