← 返回题目列表

Codeforces · 1599/H

H. 隐藏堡垒

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

这是一个交互问题!

作为你在伟大泡沫战争中贡献的一部分,你的任务是寻找新建的敌人堡垒。你生活的世界是一个巨大的 $$$10^9 \times 10^9$$$ 网格,正方形的坐标都在 $$$1$$$ 和 $$$10^9$$$ 之间。

你知道敌人的基地是一个矩形,其边与网格的边平行。你的世界的人们非常害怕处于世界的边缘,所以你知道基地不包含网格边缘的任何正方形($$$x$$$ 或 $$$y$$$ 坐标为 $$$1$$$ 或 $$$10^9$$$)。

为了帮助您找到基地,您获得了一个设备,您可以将其放置在网格的任何方块中,它会告诉您曼哈顿到基地最近的方块的距离。从方格 $$$(a, b)$$$ 到方格 $$$(p, q)$$$ 的曼哈顿距离计算为 $$$|a−p|+|b−q|$$$。如果您尝试将该设备放置在敌方基地内,您将被敌人俘获。因此,您需要确保永远不要将该设备放置在敌方基地内。

遗憾的是,该设备由电池供电,无法充电。这意味着您最多可以使用该设备 $$$40$$$ 次。

输入

输入包含您查询的答案。

互动

您的代码可以通过编写“? $$$i$$$ $$$j$$$” $$$(1 \leq i,j \leq 10^9)$$$ 将设备放置在网格中的任何方块上。作为回报,如果您放置设备的方格位于敌方基地内部或网格外部,它将接收从方格 $$$(i,j)$$$ 或 $$$-1$$$ 到敌方基地最近方格的曼哈顿距离。

如果您收到 $$$-1$$$ 而不是正数,请立即退出,您将看到错误的答案判决。否则,您可以获得任意判决,因为您的解决方案将继续从关闭的流中读取。

您的解决方案使用的查询不应超过 $$$40$$$。

一旦你确定了敌人基地的位置,你应该打印 "! $$$x$$$ $$$y$$$ $$$p$$$ $$$q$$$" $$$(1 \leq x \leq p\leq 10^9, 1 \leq y \leq q\leq 10^9)$$$,其中 $$$(x, y)$$$ 是$$$x$$$ 和 $$$y$$$ 坐标最小的敌方基地内的方格,$$$(p, q)$$$ 是敌方基地内 $$$x$$$ 和 $$$y$$$ 坐标最大的方格。请注意,回答不算作 40 个查询之一。

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

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

示例

输入 #1

1
1
2
1

输出 #1

? 2 2
? 5 5
? 4 7
? 1 5
! 2 3 4 5