Submission #68871

#	Time	Username	Problem	Language	Result	Execution time	Memory
68871		alenam0161	The Big Prize (IOI17_prize)	C++17	100 / 100	85 ms	7748 KiB

prize

#include "prize.h"
#include <bits/stdc++.h>
using namespace std;
const int N = 3e5+7;
vector<int> ans[N];
int rs=-1;
int gdl,gdr;
vector<int> get(int x){
    if(ans[x].size()==0){
        ans[x]=ask(x);
        if(ans[x][0]==0&&ans[x][1]==0){
            rs=x;
            return ans[x];
        }
        if(ans[x][0]==0)gdl=max(gdl,x);
        if(ans[x][1]==0)gdr=min(gdr,x);
   // cout<<x<<" "<<ans[x][0]<<" "<<ans[x][1]<<endl;
    }
    return ans[x];
}
void fnd(int l,int r){
    if(rs!=-1)return;
    if(l==r){
        if(gdl<=l&&l<=gdr)
        get(l);
        return;
    }
    if(l+1==r){
        return;
    }
    int m=(l+r)/2;
    if(gdl>=m){
        fnd(m,r);
        return;
    }
    if(gdr<=m){
        fnd(l,m);
        return;
    }
    vector<int> lres=get(l);
    if(rs!=-1)return;
    vector<int> rres=get(r);
    if(rs!=-1)return;
    if(lres[0]==rres[0]&&lres[1]==rres[1])return;
    if(lres[1]==0||rres[0]==0)return;
    vector<int> md=get(m);
    if(rs!=-1)return;
    if(rand()&1){
        if(md[0]!=0)fnd(l,m);
        if(rs!=-1)return;
        if(md[1]!=0)fnd(m,r);
    }
    else{
        if(md[1]!=0)fnd(m,r);
        if(rs!=-1)return;
        if(md[0]!=0)fnd(l,m);
    }
}
int find_best(int n) {
    srand(6451719);
    gdl=-1;
    gdr=n;
    fnd(0,n-1);
    return rs;

    int i;
	for(i = 0; i < n; i++) {
		std::vector<int> res = get(i);
	//	cout<<i<<" ok "<<res[0]<<" "<<res[1]<<endl;
		if(res[0] + res[1] == 0)
			return i;
        int cur=i;
        int brd=20;
        if(res[0]+res[1]<n/2)brd=3;
        else brd=20;

        for(int j=brd;j>=0;j--){
            int rg=cur;
            rg+=1<<j;
            if(rg<n){
                vector<int> cres=get(rg);
              //  cout<<rg<<" "<<cur<<" "<<j<<" ok "<<cres[0]<<" "<<cres[1]<<endl;
                if(cres[0]+cres[1]==0)return rg;
                if(res[0]==cres[0]&&res[1]==cres[1]){
                    cur=rg;
                    continue;
                }
                if(cres[0]==0){
                    cur=rg;
                    continue;
                }
            }
        }
        i=cur;
	}
	return n-1;
}

• Subtask 1: 20 / 20
• Subtask 2: 80 / 80