这是一个交互问题。
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$$$ 是
| 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 | 请注意,网格不必完全相同,但必须满足 $$$\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 |