Submission #255027

#TimeUsernameProblemLanguageResultExecution timeMemory
255027tinjyuThe Big Prize (IOI17_prize)C++14
98.13 / 100
51 ms1920 KiB
#include "prize.h" #include <bits/stdc++.h> using namespace std; int m,ball=0,a[200005][2],ans=-1; int find(int x) { if(a[x][0]==-1) { std::vector<int> res = ask(x); a[x][0]=res[0]; a[x][1]=res[1]; } return 0; } int solve(int s,int e){ //cout<<s<<" "<<e<<endl; if(s>=e-1)return 0; if(ans!=-1)return 0; int ne,ns,c1=1,c2=1; ne=(s+e)/2,ns=(s+e)/2; while(ns<e) { find(ns); if(a[ns][0]+a[ns][1]==0) { ans=ns; return 0; } if(a[ns][0]+a[ns][1]!=ball) { if(a[ns][1]==0) { c1=0; break; } ns++; } else break; } while(s<ne) { find(ne); if(a[ne][0]+a[ne][1]==0) { ans=ne; break; } if(a[ne][0]+a[ne][1]!=ball) { if(a[ne][0]==0) { c2=0; break; } ne--; } else break; } //cout<<ne<<" "<<ns<<endl; if(c1==1 && a[ns][1]!=a[e][1])solve(ns,e); if(c2==1 && a[s][0]!=a[ne][0])solve(s,ne); } int find_best(int n) { for(int i=0;i<n;i++) { a[i][0]=-1; a[i][1]=-1; } for(int i=0;i<min(n,100);i++)find(i); for(int i=n-1;i>=max(n-100,0);i--)find(i); for(int t = 0; t < 250; t++) { long long int i=rand(); i%=n; find(i); //cout<<a[i][0]<<" "<<a[i][1]<<endl; if(a[i][0]+a[i][1]==0) { ans=i; break; } if(a[i][0] + a[i][1] > ball) { m=i; ball=a[i][0]+a[i][1]; } } if(ans!=-1)return ans; // cout<<m<<endl; int start=0,end=n-1; while(true) { find(start); if(a[start][0]+a[start][1]==0)ans=start; if(a[start][0]+a[start][1]!=ball)start++; else break; } while(true) { find(end); if(a[end][0]+a[end][1]==0)ans=end; if(a[end][0]+a[end][1]!=ball)end--; else break; } if(ans!=-1)return ans; //cout<<start<<" "<<end<<endl; solve(start,m); solve(m,end); return ans; }

Compilation message (stderr)

prize.cpp: In function 'int solve(int, int)':
prize.cpp:65:1: warning: control reaches end of non-void function [-Wreturn-type]
 }
 ^
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...