Submission #103371

#TimeUsernameProblemLanguageResultExecution timeMemory
103371daniel920712The Big Prize (IOI17_prize)C++14
90 / 100
70 ms2068 KiB
#include <iostream> #include <stdio.h> #include <math.h> #include <assert.h> #include "prize.h" using namespace std; int all[200005]; int l[200005],r[200005]; int ans=0; int F(int L,int R) { //printf("%d %d\n",L,R); vector < int > t; int x; if(l[(L+R)/2]==-1) { ans++; assert(ans<=10000); t=ask((L+R)/2); l[(L+R)/2]=t[0]; r[(L+R)/2]=t[1]; } if(l[R]==-1) { ans++; assert(ans<=10000); t=ask(R); l[R]=t[0]; r[R]=t[1]; } if(l[L]==-1) { ans++; assert(ans<=10000); t=ask(L); l[L]=t[0]; r[L]=t[1]; } if(l[L]==0&&r[L]==0) return L; if(l[R]==0&&r[R]==0) return R; if(l[(L+R)/2]==0&&r[(L+R)/2]==0) return (L+R)/2; if(L==R) { if(l[L]||r[L]) return -1; return L; } else if(L+1==R) { if(l[L]||r[L]) { if(l[R]||r[R]) return -1; return R; } return L; } else { //printf("%d %d %d %d %d %d\n",l[L],r[L],l[(L+R)/2],r) if(r[R]==r[(L+R)/2]) return F(L,(L+R)/2); else if(l[L]==l[(L+R)/2]) return F((L+R)/2+1,R); else { x=F((L+R)/2+1,R); if(x!=-1) return x; return F(L,(L+R)/2); } } } int find_best(int n) { vector < int > t; int i,j,all=0; for(i=0;i<n;i++) l[i]=r[i]=-1; ans++; assert(ans<=10000); t=ask(0); l[0]=t[0]; r[0]=t[1]; ans++; assert(ans<=10000); t=ask(n-1); l[n-1]=t[0]; r[n-1]=t[1]; return F(0,n-1); }

Compilation message (stderr)

prize.cpp: In function 'int find_best(int)':
prize.cpp:75:11: warning: unused variable 'j' [-Wunused-variable]
     int i,j,all=0;
           ^
prize.cpp:75:13: warning: unused variable 'all' [-Wunused-variable]
     int i,j,all=0;
             ^~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...