题解 CF843B 【Interactive LowerBound】

zi小眼聚光 · 2019-05-01 19:51:23 · 题解

显然没法把整个链表读进来

分块做就好啦！（滑稽）

随机询问1000次，找到最大的不大于x的数，并记录nxt

因为是随机的且1000<<50000，所以基本上问到的这1000个点是在链表中均匀分布的

于是最好情况下链表被分成了50块，这时你还有999次询问，而你已经大概知道答案在哪块！

证明概率的话，因为询问了1000次，每次都不在x向前的1000节点的概率大概是(1-999/n)^1^0^0^0 ，脸不白都能过（虽说我连着wa了两次）

愉快的附上代码：

#include<cstdio>
#include<algorithm>
using namespace std;
int n,start,x,nxt,ans=-1,a,b;
bool use[500005];
struct mker{//随机数怕被卡结果还是被卡了233
    int seed0,seed1,seed2;
    mker(){
        seed0=*(new int);
        seed1=*(new int);
        seed2=*(new int);
    }
    unsigned int rd(){
        seed0^=seed1^=seed2;
        seed0=(seed1<<3)|(seed2>>2)+rand();
        seed1=(seed0>>3)&(seed2<<1)-rand();
        seed2=(seed1<<4)^(seed0>>1)*rand();
        return seed0%n;
    }
}mk;
int main(){
    scanf("%d%d%d",&n,&start,&x);
    nxt=start;
    for(int i=1;i<min(n,1000);i++){
        int q=(n+mk.rd())%n+1;
        printf("? %d\n",q);
        fflush(stdout);
        scanf("%d%d",&a,&b);
        if(a<=x&&(ans==-1||a>ans)){
            nxt=b;
            ans=a;
        }
    }
    if(ans!=x){
        for(int i=1;i<=1000;i++){
            if(nxt==-1)break;
            printf("? %d\n",nxt);
            fflush(stdout);
            scanf("%d%d",&a,&b);
            nxt=b;
            if(a>=x){
                ans=a;
                break;
            }
            fflush(stdout);
        }
    }
    if(ans<x)ans=-1;
    printf("! %d\n",ans);
    fflush(stdout);
    return 0;
}