题解：P12797 [NERC 2022] Hot and Cold

神秘方言题。

显然是二进制拆分的思路。题目要求 $64$ 次询问出结果。那么由于范围最大达 $10^6$，则每次询问通过 $3 \times \log(10^6)\approx3 \times 20=60$ 可知只能询问 $3$ 次。所以剩下有 $4$ 次机会来确定方言。

我们询问 $3$ 次问出词义，通过询问 $3$ 次分别为 $(0,0)$，$(1,1)$，$(0,0)$，确定 $(1,1)$ 和 $(0,0)$ 离目标点的关系。

若已经找到，则停止。该步骤之后每次询问之后都要加，不再赘述。

若没找到，即结尾不是感叹号，则如果两次字符串结果相同，则答案一定在 $(1,0)$ 和 $(0,1)$ 之间，直接询问即可。

否则我们知道答案一定不是 $(1,0)$ 或 $(0,1)$，则 $(1,1)$ 询问的结果一定是更近，$(0,0)$ 询问的结果一定是更远。

所以 $3$ 次可以确定词义。

接下来，每次缩小范围只能询问 $3$ 次，如果可以询问 $4$ 次可能这题就是个绿。我们把 $x$ 和 $y$ 的操作一起算，就可以减掉分开算的多余操作。

询问当前范围中心点，在询问中心点上面一个点（相距 $1$ 单位长度），然后在询问中心点右上角的那个点，可以确定下来目标点在中心点哪个方向。即：
记此时的范围是 $(lx,ly)$ 到 $(rx,ry)$，则定义 $midx=\frac{lx+rx}{2},miny=\frac{ly+ry}{2}$，$(midx,midy)$ 即为中心点。再询问 $(midx,midy+1)$，可以确定目标点在中心点的上面还是下面。我们假设是在上面，下面同理。然后询问 $(midx+1,midy+1)$，则可以确定目标点是在中心点上方的左边还是右边。

所以 $3$ 次操作可以把 $x$ 和 $y$ 均砍一半，则总的询问次数为 $3 \times \log(10^6)\approx3 \times 20=60$，加上确定词义的 $3$ 次，共 $63$ 次，可以通过。