题解：P12797 [NERC 2022] Hot and Cold

首先考虑如果我们知道每个单词是什么含义，这时该怎么做。

先从一维的情况开始考虑，不难发现可以二分。

在当前区域内，每次取中点和中点右面的点，如果得到的回复是“Closer”说明在中点右面，反之则在中点左面。

一个维度的二分次数为 $2 \times \log_210^6$，是 $40$ 次。对两个维度分别做二分，需要的次数是 $80$。

这样做是对的，但超过了 $64$。原因是我们对两个维度分别做二分，对一个维度二分时会浪费另一个维度的信息。我们考虑对两个维度同时做二分。

取平面中点，再取中点上方的点，如果回复“Closer”说明宝藏在中点上方，反之在中点下方。然后取中点右上方的点，如果回复“Closer”说明在中点右侧，反之则在中点左侧。

这样做只需要取 $3$ 个点就对两个维度同时进行了二分。最后需要的次数是 $60$，小于 $64$ 次，非常成功。

现在我们并不知道每个单词是什么含义，我们考虑如何知道。

带感叹号的一定是“Found!”，第一个出现的一定是“Not Found”。我们只需要区分“Closer”“Further”和“At the same distance”即可。

取 $(0, 0)$ 作为第一个点，取 $(1, 1)$ 作为第二个点，这时得到的回复要么是“Closer”要么是“At the same distance”。

然后我们再取回 $(0, 0)$，如果得到的回复和刚才不同，那么刚才的回复是“Closer”，现在的回复是“Further”，那个没出现的回复就是“At the same distance”。这时用了 $3$ 次询问，加上刚才的 $60$ 次，总共 $63$ 次，没有超过 $64$。

如果相同的话，说明这个回复是“At the same distance”，那么宝藏一定在 $(0, 1)$ 或 $(1, 0)$ 的位置，分别询问即可。