← 返回题目列表

Codeforces · 1153/E

E. 薮和蛇

中文机器翻译题面 查看原题

这是一个交互问题。

现在 Serval 是 Japari 中学的一名高中生。然而,在去学校的路上,他必须穿过一个池塘,里面有一条危险的蛇。池塘可以表示为 $$$n \times n$$$ 网格。蛇的头和尾位于不同的细胞中,它的身体是一系列连接头和尾的相邻细胞而不自相交。如果薮猫撞到它的头或尾巴,蛇就会咬他,他就会死。

幸运的是,他有一个特殊的设备可以回答以下问题:你可以选择一个矩形,它会告诉你沿着蛇从头到尾逐个单元地行走需要穿过矩形边界的次数。下面的图片显示了一条可能的蛇以及对其的可能查询,这将得到 $$$4$$$ 的答案。

今天Serval起得太晚了,只有时间进行$$$2019$$$查询。作为他最好的朋友,你能帮他找到头部和尾部的位置吗?

请注意,当且仅当两个单元格在网格中具有公共边时,它们才是相邻的,并且蛇的身体长度可以为 $$$0$$$,这意味着它只有相邻的头和尾。

另请注意,蛇正在睡觉,因此当薮猫使用他的设备时它不会移动。显而易见的是,蛇的位置并不取决于您的查询。

输入

第一行包含一个整数 $$$n$$$ ($$$2\leq n \leq 1000$$$) — 网格的大小。

互动

要进行查询,您应该打印 ? x1 y1 x2 y2 ($$$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$$$。您将得到一个整数作为答案。

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

- C++ 中的 fflush(stdout) 或 cout.flush();
- Java 中的 System.out.flush();
- 帕斯卡刷新(输出);
- Python 中的 stdout.flush() ;
- 请参阅其他语言的文档。

回答$$$-1$$$而不是有效答案意味着您进行了无效查询或超出了最大查询数。收到$$$-1$$$后立即退出,您将看到错误的答案判决。否则,您可以获得任意判决,因为您的解决方案将继续从关闭的流中读取。

如果你的程序无法正确找出蛇的头和尾,你也会得到错误答案的判决。

黑客

要进行破解,请在第一行打印一个整数 $$$n$$$ ($$$2 \leq n \leq 1000$$$),指示网格的大小。

然后在第二行打印一个整数$$$k$$$ ($$$2 \leq k \leq n^2$$$),表示蛇的长度。

在接下来的 $$$k$$$ 行中,打印 $$$k$$$ 整数对 $$$x_i, y_i$$$ ($$$1 \leq x_i, y_i \leq n$$$),每对在一行中,表示蛇的第 $$$i$$$ 个单元格,使得相邻对相邻,并且所有 $$$k$$$ 对都是不同的。

输出

当您准备好回答时,您应该打印! x1 y1 x2 y2,其中$$$(x_1, y_1)$$$表示头部位置,$$$(x_2,y_2)$$$表示尾部位置。您可以按任意顺序打印头部和尾部。

示例

输入 #1

2

1

0

0

输出 #1

? 1 1 1 1

? 1 2 1 2

? 2 2 2 2

! 1 1 2 1

输入 #2

3

2

0

输出 #2

? 2 2 2 2

? 2 1 2 3

! 2 1 2 3

注意

上面的图片显示了我们在第一个示例中的查询和答案。我们首先查询 $$$(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,1)$$$ 到 $$$(2,3)$$$ 的矩形。由于第一个答案是 $$$2$$$,$$$(2,1)$$$ 和 $$$(2,3)$$$ 都必须被占用,但其他都不能被占用,所以答案是 $$$(2,1)$$$ 和 $$$(2,3)$$$。