Submission #432563

#	Time	Username	Problem	Language	Result	Execution time	Memory
432563		plekkpea	The Big Prize (IOI17_prize)	C++14	100 / 100	70 ms	11300 KiB

prize

#include "prize.h"
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
vector<int> kaes[200005];
ll su,ma=0,x;

int rek(ll l,ll r,ll a,ll b){
    if(r<l || l<0 ) return -1;
    ll k=(l+r)/2,x,arv;
    bool en=0,par=0;
    if(kaes[k][0]==-1) kaes[k]=ask(k);
    if(kaes[k][0]+kaes[k][1]==0) return k;
    x=k;
    if(kaes[x][0]==a) en=1;
    if(kaes[x][0]==b) par=1;
    while(kaes[x][0]+kaes[x][1]<su){
        x++;
        if(x==r+1) break;
        if(kaes[x][0]==-1) kaes[x]=ask(x);
        if(kaes[x][0]+kaes[x][1]==0) return x;
        if(kaes[x][0]==a) en=1;
        if(kaes[x][0]==b) par=1;
    }
    if(x==r+1){
        x=k;
        while(kaes[x][0]+kaes[x][1]<su){
            x--;
            if(x==l-1) break;
            if(kaes[x][0]==-1) kaes[x]=ask(x);
            if(kaes[x][0]+kaes[x][1]==0) return x;
            if(kaes[x][0]==a) en=1;
            if(kaes[x][0]==b) par=1;
        }
    }
    if(x<l) return -1;
    if(!en){
        if(x<=k) arv=rek(l,x-1,a,kaes[x][0]);
        else arv=rek(l,k-1,a,kaes[x][0]-(x-k));
        if(arv!=-1) return arv;
    }
    if(!par){
        if(x>=k) arv=rek(x+1,r,kaes[x][0],b);
        else arv=rek(k+1,r,kaes[x][0]-(k-x),b);
        if(arv!=-1) return arv;
    }
    return -1;
}

int find_best(int n) {
    ll l=0, r=n-1;
    vector<int> res;
    for(int i=0; i<10; i++){
        x=(rand())%n;
        res=ask(x);
        su=res[0]+res[1];
        kaes[x]=res;
        ma=max(ma,su);
        if(su==0) return x;
    }
    for(int i=0; i<n; i++) kaes[i].resize(2),kaes[i][0]=-1;
    return rek(l,r,0,su);
}

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