题目概述

交互题，让你猜两个 $[1,n]$ 的数 $a,b$ ，每次会回复四种情况之一，如果多条满足随机回复一条合法的：

0. $x=a,y=b$ 。
1. $x<a$ 。
2. $y<b$ 。
3. $x>a\lor y>b$ 。

$600$ 次内猜中，$n\le 10^{18}$ 。

解题报告

神题，这个随机回复和第三种情况是真的有毒，题解也没看懂，然后就去看AC代码，好像都长这样：记录 $x,len_x,y,len_y$ ，每次询问 $(x+len_x,y+len_y)$ ：

• 情况 $1$ ：$x=x+len_x,len_x=min\{2len_x,n-x\}$ 。
• 情况 $2$ ：$y=y+len_y,len_y=min\{2len_y,n-y\}$ 。
• 情况 $3$ ：$len_x=max\{ {len_x\over 2},1\},len_y=max\{ {len_y\over 2},1\}$ 。

由于情况 $1$ 和情况 $2$ 是确定的，所以可以直接倍增继续做。而情况 $3$ 是不确定的，于是只能两个都拉下水。

感觉次数极其玄学啊，接近 $O(log_2^2n)$ ？？？但是远远达不到，反正CF数据跑过了……

示例程序

#include<cstdio>
using namespace std;
typedef long long LL;

LL n,x,Lx,y,Ly;

inline int Ask(LL A,LL B) {printf("%lld %lld\n",A,B);fflush(stdout);int x;scanf("%d",&x);return x;}
int main(){
    scanf("%lld",&n);x=0;Lx=1;y=0;Ly=1;
    while (x<n||y<n){
        int now=Ask(x+Lx,y+Ly);if (!now) return 0;
        if (now==1) x+=Lx,(Lx<<1)>n-x?Lx=n-x:Lx<<=1;
        else if (now==2) y+=Ly,(Ly<<1)>n-y?Ly=n-y:Ly<<=1;
        else Lx>>1?Lx>>=1:Lx=1,Ly>>1?Ly>>=1:Ly=1;
    }return 0;
}