【题解】P3839 [IOI2017] The Big Prize

phigy · 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;
}