CF1153E Serval and Snake

这是一个交互题。 现在 Serval 是 Japari 中学的一名高中生。然而，在去学校的路上，他必须穿过一个池塘，池塘里有一条危险的蛇。池塘可以表示为一个 $n \times n$ 的网格。蛇有一个头和一个尾，分别位于不同的格子中，蛇的身体是一系列相邻的格子，将头和尾连接起来，且不会自交。如果 Serval 碰到蛇的头或尾，蛇会咬他，他就会死。 幸运的是，他有一个特殊的装置，可以回答如下问题：你可以选择一个矩形区域，装置会告诉你，从蛇头到蛇尾沿着蛇的身体一格一格走时，需要穿过这个矩形边界的次数。下图展示了一条可能的蛇和一次对它的查询，答案为 $4$。   今天 Serval 起得太晚了，只能进行 $2019$ 次查询。作为他最好的朋友，你能帮他找出蛇头和蛇尾的位置吗？ 注意，只有当两个格子有公共边时才算相邻，蛇的身体长度可以为 $0$，也就是说蛇只有头和尾且它们相邻。 另外，蛇正在睡觉，在 Serval 使用装置时不会移动。显然，蛇的位置与你的查询无关。

第一行包含一个整数 $n$（$2 \leq n \leq 1000$），表示网格的大小。

当你准备好回答时，应输出 `! x_1 y_1 x_2 y_2`，其中 $(x_1, y_1)$ 表示蛇头的位置，$(x_2, y_2)$ 表示蛇尾的位置。蛇头和蛇尾的位置顺序可以任意。 交互说明 进行一次查询时，你应输出 `? x_1 y_1 x_2 y_2`（$1 \leq x_1 \leq x_2 \leq n$，$1 \leq y_1 \leq y_2 \leq n$），表示一个包含所有 $(x, y)$ 满足 $x_1 \leq x \leq x_2$ 且 $y_1 \leq y \leq y_2$ 的矩形区域。你将获得一个整数作为回答。 每次输出查询后，不要忘记输出换行并刷新输出，否则会因“Idleness limit exceeded”而失败。具体刷新方法如下： - C++：fflush(stdout) 或 cout.flush() - Java：System.out.flush() - Pascal：flush(output) - Python：stdout.flush() - 其他语言请查阅相关文档 如果你输出了非法查询或超过了最大查询次数，返回值将为 $-1$。收到 $-1$ 后应立即退出，否则会收到 Wrong Answer 判决。否则，如果你的程序继续从已关闭的流读取数据，可能会得到任意判决。 如果你的程序未能正确找出蛇头和蛇尾的位置，也会收到 Wrong Answer 判决。 Hack 说明 进行 Hack 时，第一行输出一个整数 $n$（$2 \leq n \leq 1000$），表示网格大小。 第二行输出一个整数 $k$（$2 \leq k \leq n^2$），表示蛇的长度。 接下来的 $k$ 行，每行输出一对整数 $x_i, y_i$（$1 \leq x_i, y_i \leq n$），表示蛇的第 $i$ 个格子。相邻的格子必须相邻，且所有 $k$ 个格子都不相同。

    上图展示了第一个样例中的查询和答案。我们首先对 $(1,1)$ 进行了查询，得到答案 $1$，于是知道它必须与另一个格子相连。然后我们对 $(1,2)$ 查询，得到答案 $0$，于是知道蛇从未经过这里。因此，与 $(1,1)$ 相连的格子只能是 $(2,1)$。接着我们对 $(2,2)$ 查询，得到答案 $0$，也知道蛇从未经过 $(2,2)$。所以蛇无法离开 $(2,1)$，这意味着答案是 $(1,1)$ 和 $(2,1)$。    上图展示了第二个样例中的查询和答案。通过对 $(2,2)$ 查询并得到 $2$，我们发现蛇占据了 $(2,2)$。再对从 $(2,1)$ 到 $(2,3)$ 的矩形查询，得到答案 $0$，于是知道蛇从未离开这个矩形。由于第一个答案是 $2$，说明 $(2,1)$ 和 $(2,3)$ 都被蛇占据，其他格子没有被占据，所以答案是 $(2,1)$ 和 $(2,3)$。 由 ChatGPT 4.1 翻译