← 返回题目列表

Codeforces · 2179/G

G. Blackslex 和企鹅迁徙

中文机器翻译题面 查看原题
IOI 2025 - 迁移

这是一个交互问题。

Blackslex 正在研究的企鹅物种生活在一个岛屿上,该岛屿是一个由 $$$n$$$ 行和 $$$n$$$ 列组成的网格。网格的每个单元格中都生活着一只企鹅。

他将每只企鹅标记为从 $$$1$$$ 到 $$$n^2$$$ 的整数。一段时间后,一些企鹅迁移到另一个牢房。迁移后,每只企鹅仍会位于网格上的某个单元格中,并且每个单元格中恰好包含一只企鹅。他需要每只企鹅的当前位置。

为此,他可以询问一只企鹅与另一只企鹅的距离有多远。

正式地,对于表示所有企鹅位置的可能网格 $$$x$$$,将 $$$\operatorname{dist}(x, i, j)$$$ 表示为 $$$x$$$$$$^{\text{*}}$$$ 中企鹅 $$$i$$$ 到企鹅 $$$j$$$ 的曼哈顿距离。

有一个隐藏网格 $$$a$$$,其中包含 $$$n$$$ 行和 $$$n$$$ 列。你需要找到一个满足$$$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{*}}$$$令$$$r_i$$$、$$$c_i$$$表示企鹅$$$i$$$所在的行和列,$$$r_j$$$、$$$c_j$$$也表示相同,则曼哈顿距离为$$$|r_i - r_j| + |c_i - c_j|$$$。

输入

每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \leq t \leq 200$$$)。测试用例的描述如下。

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

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

互动

要提出查询,请选择两个整数 $$$i$$$, $$$j$$$ ($$$1 \leq i, j \leq n^2$$$) 并打印 "? $$$i$$$ $$$j$$$" (不带引号)到一行。

您将收到一个整数,它是企鹅 $$$i$$$ 和 $$$j$$$ 之间的距离。

在每个测试用例中,您最多可以进行 $$$3n^2 + 150$$$ 查询。

查询完成后,输出“!" 一行,然后输出 $$$n$$$ 行,每行包含 $$$n$$$ 个整数,第 $$$i$$$ 行上的第 $$$j$$$ 个整数为 $$$b_{i,j}$$$。

您的输出必须满足给定的条件,并且如果可能有多个,您可以输出任何此类 $$$b$$$。请注意,这是 不 被认为是一个查询,并且是 不 在计算询问的数量时考虑在内。

此后,继续下一个测试用例。

此任务中的交互器是 不自适应。换句话说,交互过程中网格不会发生变化。

如果您在交互期间在测试用例中进行了超过 $$$3n^2 + 150$$$ 查询,您的程序必须立即终止,并且您将收到错误答案判决。否则,您可以获得任意判决,因为您的解决方案将继续从关闭的流中读取。

打印查询后,不要忘记输出行尾并刷新输出。否则,你会得到 超出空闲限制。为此,请使用:

  • fflush(标准输出) or cout.flush() 在 C++ 中;
  • System.out.flush() 在 Java 中;
  • 冲洗(输出) 帕斯卡;
  • stdout.flush() 在 Python 中;
  • 请参阅其他语言的文档。

黑客

要破解,请遵循以下测试格式。

第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 200$$$)。测试用例的描述如下。

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

接下来的 $$$n$$$ 行包含 $$$n$$$ 整数,第 $$$i$$$ 行上的第 $$$j$$$ 整数是 $$$a_{i,j}$$$ — 行 $$$i$$$、$$$j$$$ 列的企鹅标签。

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

示例

输入
复制

2
2

1

2

1

1

2

1

3

3

输出
复制

? 1 2

? 1 3

? 1 4

? 2 3

? 2 4

? 3 4

!
3 4
2 1

? 1 8

!
9 1 3
4 2 7
8 5 6

注意

请注意,附加行是为了便于阅读。您的解决方案不应输出这些附加行。

在第一个测试用例中,网格 $$$a$$$ 是

14
23

在第二个测试用例中,网格 $$$a$$$ 是

913
427
856

交互如下。

参赛者法官说明
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请注意,网格不必完全相同,但必须满足 $$$\operatorname{dist}(a, i, j) = \operatorname{dist}(b, i, j)$$$ 对于所有 $$$1 \leq i, j \leq n^2$$$。
2 1
3第二个测试用例开始。该岛的大小为 $$$n=3$$$。
? 1 8参赛者询问标记为 $$$1$$$ 和 $$$8$$$ 的企鹅的距离。
3标记为 $$$1$$$ 和 $$$8$$$ 的企鹅的距离是 $$$3$$$。
!参赛者确定了一个可能的网格$$$b$$$。
9 1 3
4 2 7
8 5 6