题目翻译

有一个数 $x$，你可以询问至多 $60$ 次，每次会返回 $0,1,-1$ 中的任意一个数。 $1$ 代表询问的数 $>x$，$-1$ 代表询问的数 $<x$，$0$ 代表询问的数 $=x$。

有时候可能会返回错误的信息，可能会 $1$ 和 $-1$ 交换。但相等时，是不会返回错误信息的。信息返回的周期长度为 $n$。

本题注意事项：

• 得到 $0$ 或 $-1$ 返回时，立即终止程序。
• 本题是交互题，输出后需要 fflush(stdout);（C++ 之外的语言请自行查看原题面）。

题目思路

至多 $60$ 次，范围在 $1\leq x\leq 1\times 10^9$ 内，明显是二分。

已知一个三十二位有符号整数（C++ 的 int）上限为 $2^{31}-1=2,147,483,647$，所以二分算法最坏情况大约要 $30$ 次查询。

但这还不够，我们要知道，每次返回是正确的还是错误的。正好 $n\leq 30$，加上二分次数正好 $60$。

我们查询 $n$ 次，每次询问 $1$。$1$ 只可能返回 $1$ 或 $0$，那么 $-1$ 即为错误的。

知道了每次信息是否正确，就能进行二分了。

完整代码

#include<bits/stdc++.h>
using namespace std;
bool f[50];
int main()
{
    int n,m,cnt=0;
    cin>>n>>m;
    for(int i=0;i<n;i++)
    {
        cout<<1<<endl;
        fflush(stdout);
        int x;
        cin>>x;
        if(x==-1)f[i]=0;
        else if(x==1)f[i]=1;
        else return 0;
    }
    int mid,x,l=2,r=m;
    while(l<=r)
    {
        cnt%=n;
        mid=(l+r)/2;
        cout<<mid<<endl;
        fflush(stdout);
        cin>>x;
        if(f[cnt]==0&&x==-1||f[cnt]==1&&x==1)l=mid+1;
        else if(f[cnt]==0&&x==1||f[cnt]==1&&x==-1)r=mid-1;
        else if(x==-2||x==0)return 0;
        cnt++;
    }
    return 0;
}