Submission #131495

#	Time	Username	Problem	Language	Result	Execution time	Memory
131495		20160161simone	The Big Prize (IOI17_prize)	C++14	20 / 100	78 ms	2168 KiB

prize

#include<iostream>
#include<cstring>
#include<cstdio>
#include<vector>
#include<ctime>
#include<cstdlib>
#include<algorithm>
#include "prize.h"
using namespace std;
vector<int> res;
#define Maxn 200010
bool flag[Maxn];
int ans[Maxn][2];
int maxv=0,pos;
int answer;
void Ask(int x){
    if(flag[x])return;
    flag[x]=true;
    res=ask(x);
    ans[x][0]=res[0];ans[x][1]=res[1];
}
void solve(int l,int r,int ed,int val){
    if(l==r){
        Ask(l);
        if(ans[l][0]==0&&ans[l][1]==0)answer=l;
        return;
    }
    int mid=(l+r)>>1;
    if(ed==-1){
        solve(l,mid,ed,mid-l+1);
        solve(mid+1,r,ed,r-mid);
        return;
    }
    if(ed<=mid){
        if(val-(r-mid))solve(l,mid,ed,val-(r-mid));
        solve(mid+1,r,-1,r-mid);
        return;
    }
    int tmp=-1;
    for(int i=mid;i>=l;--i){
        Ask(i);
        if(ans[i][0]+ans[i][1]==maxv){
            tmp=i;
            break;
        }
    }
    if(tmp==-1){
        solve(l,mid,-1,mid-l+1);
        if(val-(mid-l+1))solve(mid+1,r,ed,val-(mid-l+1));
        return;
    }
    int now=ans[ed][0]-ans[tmp][0]-(mid-tmp)+r-ed;
    if(now)solve(mid+1,r,ed,now);
    now=val-now;
    if(now)solve(l,mid,tmp,now);
}
int find_best(int n){
    srand(time(NULL));
    for(register int i=1;i<=100;++i){
        int x=1ll*rand()*rand()%n;
        Ask(x);
        maxv=max(maxv,ans[x][0]+ans[x][1]);
    }
    int last;
    for(register int i=n-1;i>=0;--i){
        Ask(i);
        if(ans[i][0]==0&&ans[i][1]==0)return i;
        if(ans[i][0]+ans[i][1]==maxv){
            last=i;
            break;
        }
    }
    solve(0,n-1,last,ans[last][0]+ans[last][1]);
    return answer;
}

Compilation message (stderr)

prize.cpp: In function 'int find_best(int)':
prize.cpp:64:9: warning: 'last' may be used uninitialized in this function [-Wmaybe-uninitialized]
     int last;
         ^~~~

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