[BalticOI 2018] 蠕虫之忧
题目描述
**题目译自 [BalticOI 2018](https://boi2018.progolymp.se/tasks/) Day1「[Worm Worries](https://boi18-day1-open.kattis.com/problems/boi18.worm)」**
**本题是一道交互题。**
在一个三维空间(我们限制大小为 $N\times M\times K$)内,每个点都有一个正整数参数,记这个参数为 $H[x,\, y,\, z]$(保证 $1$ $\leqslant$ $x$ $\leqslant$ $N$ $,$ $1$ $\leqslant$ $y$ $\leqslant$ $M$ $,$ $1$ $\leqslant$ $z$ $\leqslant$ $K$ 且每个参数都不超过 $10^9$)。你最多可以询问 $Q$ 次,找到一个点,使得这个点的参数大于它周围与它有公共边的所有点的参数,即:$H[x,\,y,\,z]\geqslant\max(H[x+1,\,y,\,z],$ $H[x-1,\,y,\,z],$ $H[x,\,y-1,\,z],$ $H[x,\,y-1,\,z],$ $H[x,\,y,\,z+1],$ $H[x,\,y,\,z-1]).$
特别地,当一个点不在空间直角坐标系的第一卦限内时,它的参数为 $0$。
输入输出格式
输入格式
**请使用标准输入输出流**与交互库进行交互。你可以向交互库询问最多 $Q$ 次,每次可以询问一个点的参数。
输入的第一行包含四个整数 $N,\,M,\,K,\,Q$ (请忽略这一行的其他参数)。在此之后,你可以向交互器提出至多 $Q$ 行形如 ``? x y z`` 的询问,表示“询问坐标为 $(x,\,y,\,z)$ 的点的参数是多少”。对于每一组询问,交互器会输出一行一个整数表示坐标为 $(x,\,y,\,z)$ 的点的参数。
当你找到一组解时,输出一行 ``! x y z`` 表示你找到的答案是 $(x,\,y,\,z)$,并终止程序。此时交互器不会有任何输出。
所有坐标必须满足 $1\leqslant x\leqslant N,\, 1\leqslant y\leqslant M,\, 1\leqslant z\leqslant K$。如果不满足坐标的限制、询问不符合格式或询问超过了 $Q$ 行,交互器会输出 ``-1`` 并退出,此时你的程序也应该退出。否则你可能会得到 ``Runtime Error`` 或 ``Time Limit Exceeded`` 的判定结果。
请注意,你必须在每一次询问之后手动刷新缓存,否则你的程序将会超时,对于各语言,刷新缓存的方法如下:
- Java: 调用 ``System.out.println()`` 会自动刷新缓存;
- Python: 调用 ``print()`` 会自动刷新缓存;
- C++: ``cout << endl`` 可以输出一个换行并刷新缓存。如果使用 ``printf``,请使用 ``fflush(stdout)``;
- Pascal: 调用 ``Flush(Output)``。
为了帮助你更好地完成交互,我们提供了可以复制到你的程序里的可选代码。可选代码使用了较快的输入输出,可能会提高 IO 较慢的 Python 和 Java 语言的程序效率(只与最后两个子任务有关)。
交互器没有使用随机函数,这意味着,每组测试数据都是固定的,与你的程序的询问无关。
输出格式
为了使你更好地完成交互,下面给出一组交互的示例。在这个示例中,$N=3,\,M=3,\,K=1,\,Q=3$,这三个格子的参数为 $\{10,\,14,\,13\}$。以 ``JUDGE`` 开头的行表示交互库输出的内容(你的程序的标准输入的内容),以 ``YOU`` 开头的行表示你的程序的输出。
```
JUDGE: 3 1 1 3 123123 fixed 10 14 13
YOU : ? 3 1 1
JUDGE: 13
YOU : ? 2 1 1
JUDGE: 14
YOU : ? 1 1 1
JUDGE: 10
YOU : ! 2 1 1
```
输入输出样例
暂无测试点说明
| 子任务 | 分值 | 限制 |
|:------:|:----:|:----:|
| $1$ | $10$ | $M=K=1,\,N=1\,000\,000,\,Q=10\,000$ |
| $2$ | $22$ | $M=K=1,\,N=1\,000\,000,\,Q=35$ |
| $3$ | $12$ | $K=1,\,N=M=200,\,Q=4\,000$ |
| $4$ | $19$ | $K=1,\,N=M=1\,000,\,Q=3\,500$ |
| $5$ | $14$ | $N=M=K=100,\,Q=100\,000$ |
| $6$ | $23$ | $N=M=K=500,\,Q=150\,000$ |
感谢 Hatsune_Miku 提供的翻译