CF2179G.Blackslex and Penguin Migration

IOI 2025 - Migrations

This is an interactive problem.

The species of penguins that Blackslex is researching lives on an island that is a grid with $n$ rows and $n$ columns. Exactly one penguin lives in each one cell of the grid.

He labelled each penguin as an integer from $1$ to $n^2$. After some time, some penguins migrated to another cell. After migration, every penguin will still be in some cell on the grid, and every cell contains exactly one penguin. He needs the current position of every penguin.

To do so, he can ask a penguin how far another penguin is from it.

Formally, for a possible grid $x$ representing the position of all penguins, denote $\operatorname{dist}(x, i, j)$ as the Manhattan distance of the penguin $i$ to the penguin $j$ in $x$$^{\text{∗}}$.

There is a hidden grid $a$ with $n$ rows and $n$ columns. You need to find a grid $b$ that satisfies

• $b$ has $n$ rows and $n$ columns.
• Each cell of $b$ contains an integer from $1$ to $n^2$, which is a penguin's label. Each integer will be in a single cell.
• For all $1 \leq i, j \leq n^2$, it holds that $\operatorname{dist}(a, i, j) = \operatorname{dist}(b, i, j)$.

To do so, you may make the following query no more than $3n^2 + 150$ times.

• Given $i$, $j$ ($1 \leq i, j \leq n^2$), receive the value of $\operatorname{dist}(a, i, j)$.

$^{\text{∗}}$Let $r_i$, $c_i$ denote the row and column that the penguin $i$ is in, and denote the same for $r_j$, $c_j$, then the Manhattan distance is $|r_i - r_j| + |c_i - c_j|$.

IOI 2025 - 迁徙

本题为交互式问题。

Blackslex 所研究的企鹅物种栖息于一座 $n$ 行 $n$ 列的网格状岛屿上。网格中每个单元格恰好居住着一只企鹅。

他将每只企鹅编号为 $1$ 至 $n^2$ 中的一个整数。经过一段时间后，部分企鹅迁徙到了其他单元格。迁徙完成后，每只企鹅仍位于网格中的某个单元格内，且每个单元格中恰好有一只企鹅。他需要确定每只企鹅当前所在的位置。

为此，他可以向某只企鹅询问另一只企鹅距离它有多远。

形式化地，对于一个可能的网格 $x$（表示所有企鹅的位置），记 $\operatorname{dist}(x, i, j)$ 为网格 $x$ 中企鹅 $i$ 与企鹅 $j$ 之间的曼哈顿距离$^{\text{∗}}$。

存在一个隐藏的 $n$ 行 $n$ 列网格 $a$。你需要找出一个满足如下条件的网格 $b$：

• $b$ 具有 $n$ 行 $n$ 列；
• $b$ 的每个单元格中包含一个 $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)$ 的值。

$^{\text{∗}}$设企鹅 $i$ 所在的行、列为 $r_i$、$c_i$，企鹅 $j$ 所在的行、列为 $r_j$、$c_j$，则曼哈顿距离定义为 $|r_i - r_j| + |c_i - c_j|$。

Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \leq t \leq 200$). The description of the test cases follows.

The first line of each test case contains a single integer $n$ ($2 \leq n \leq 100$) — the size of the island.

It is guaranteed that the total sum of all values of $n$ across all test cases does not exceed $500$.

每个测试包含多个测试用例。第一行包含测试用例的数量 $t$（$1 \leq t \leq 200$）。随后是各测试用例的描述。

每个测试用例的第一行包含一个整数 $n$（$2 \leq n \leq 100$）—— 表示岛屿的大小。

保证所有测试用例中 $n$ 的总和不超过 $500$。

Note that additional lines are for ease of reading. Your solution should not output these additional lines.

In the first test case, the grid $a$ is

1

4

2

3

In the second test case, the grid $a$ is

9

1

3

4

2

7

8

5

6

The interaction is as follows.

Contestant

Judge

Description

2

Start of the first test case. The island has size $n=2$.

? 1 2

The contestant asks for the distance of penguin labelled $1$ and $2$.

1

The distance of penguin labelled $1$ and $2$ is $1$.

? 1 3

The contestant asks for the distance of penguin labelled $1$ and $3$.

2

The distance of penguin labelled $1$ and $3$ is $2$.

? 1 4

The contestant asks for the distance of penguin labelled $1$ and $4$.

1

The distance of penguin labelled $1$ and $4$ is $1$.

? 2 3

The contestant asks for the distance of penguin labelled $2$ and $3$.

1

The distance of penguin labelled $2$ and $3$ is $1$.

? 2 4

The contestant asks for the distance of penguin labelled $2$ and $4$.

2

The distance of penguin labelled $2$ and $4$ is $2$.

? 3 4

The contestant asks for the distance of penguin labelled $3$ and $4$.

1

The distance of penguin labelled $3$ and $4$ is $1$.

!

The contestant determined a possible grid $b$.

3 4

Note that the grid need not be exactly the same, but it must hold that $\operatorname{dist}(a, i, j) = \operatorname{dist}(b, i, j)$ for all $1 \leq i, j \leq n^2$.

2 1

3

Start of the second test case. The island has size $n=3$.

? 1 8

The contestant asks for the distance of penguin labelled $1$ and $8$.

3

The distance of penguin labelled $1$ and $8$ is $3$.

!

The contestant determined a possible grid $b$.

9 1 3

4 2 7

8 5 6

注意：额外的空行仅为便于阅读。你的程序输出中不应包含这些额外的空行。

第一个测试用例中，网格 $a$ 为：

1

4

2

3

第二个测试用例中，网格 $a$ 为：

9

1

3

4

2

7

8

5

6

交互过程如下：

参赛者

评测机

说明

2

第一个测试用例开始。岛屿大小为 $n=2$。

? 1 2

参赛者询问编号为 $1$ 和 $2$ 的企鹅之间的距离。

1

编号为 $1$ 和 $2$ 的企鹅之间的距离为 $1$。

? 1 3

参赛者询问编号为 $1$ 和 $3$ 的企鹅之间的距离。

2

编号为 $1$ 和 $3$ 的企鹅之间的距离为 $2$。

? 1 4

参赛者询问编号为 $1$ 和 $4$ 的企鹅之间的距离。

1

编号为 $1$ 和 $4$ 的企鹅之间的距离为 $1$。

? 2 3

参赛者询问编号为 $2$ 和 $3$ 的企鹅之间的距离。

1

编号为 $2$ 和 $3$ 的企鹅之间的距离为 $1$。

? 2 4

参赛者询问编号为 $2$ 和 $4$ 的企鹅之间的距离。

2

编号为 $2$ 和 $4$ 的企鹅之间的距离为 $2$。

? 3 4

参赛者询问编号为 $3$ 和 $4$ 的企鹅之间的距离。

1

编号为 $3$ 和 $4$ 的企鹅之间的距离为 $1$。

!

参赛者确定了一个可能的网格 $b$。

3 4

注意：该网格无需与原网格完全相同，但必须满足对所有 $1 \leq i, j \leq n^2$，均有 $\operatorname{dist}(a, i, j) = \operatorname{dist}(b, i, j)$。

2 1

3

第二个测试用例开始。岛屿大小为 $n=3$。

? 1 8

参赛者询问编号为 $1$ 和 $8$ 的企鹅之间的距离。

3

编号为 $1$ 和 $8$ 的企鹅之间的距离为 $3$。

!

参赛者确定了一个可能的网格 $b$。

9 1 3

4 2 7

8 5 6