自动搬运

查看原文

来自洛谷，原作者为

	phigy 互关，私信。 What is mind?No matter.What is matter?Never mind.

搬运于2025-08-24 21:53:16，当前版本为作者最后更新于2024-12-27 09:52:05，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

设查询 $i$ 的结果是 $x_i,y_i$，那么我们可以通过 $x_i+y_i$ 的大小关系判断 $a_i$ 的大小关系。

同时对于一段 $a_i$ 相等的连续段 $x_i,y_i$ 都是一样的，也就是说我们可以二分出一个数后面第一个不同的数。

考虑 $a_i$ 最大值之外的数是少的，至多 $474$ 个。

所以直接二分出所有最大值之外的数（实际上写成分治会更好）就可以做到大约 $474\times 19=9006$，需要注意到的是我们可能需要先取 $475$ 次来知道 $a_i$ 最大值的 $x_i+y_i$。

考虑二分的常数太大了，我们强制每 $511$ 个一块，如此至多 $392$ 个块，然后每个块做二分，做到大约 $392+474\times 10=5132$。

按随机顺序取块就可以做到期望 $392+\dfrac{474}{2}\times 10=2762$。

#include <bits/stdc++.h>

#define i64 long long
#define pii pair<int,int> 

using namespace std;

const int REN=200000,MAXN=REN+5;
int B=293;
int n;
pii a[MAXN];
int mx;
pii ask(int i)
{
    if(a[i].first!=0||a[i].second!=0) {return a[i];}
    cout<<"? "<<i<<endl;
    cin>>a[i].first>>a[i].second;
    if(a[i].first==a[i].second&&a[i].second==0) {cout<<"! "<<i<<endl;exit(0);}
    return a[i];
}
void solve(int L,int R)
{
    ask(L);ask(R);
    if(R-L==1) {return ;}
    if(a[L]==a[R]) {return ;}
    int mid=(L+R)>>1;
    solve(L,mid);solve(mid,R);
}
signed main()
{
    int i,j,k;
    cin>>n;
    srand(114514);
    vector<int>tmp;
    for(i=0;i*B<n;i++)
    {
        int now=i*B,nxt=min(n-1,(i+1)*B);
        tmp.push_back(i);
        ask(now);ask(nxt);
        mx=max(mx,a[now].first+a[now].second);
        mx=max(mx,a[nxt].first+a[nxt].second);
    }
    random_shuffle(tmp.begin(),tmp.end());
    for(int i:tmp)
    {
        int now=i*B,nxt=min(n-1,(i+1)*B);
        if(a[now]!=a[nxt]) {solve(now,nxt);}
    }
    return 0;
}