Submission #429028

#TimeUsernameProblemLanguageResultExecution timeMemory
429028vanicThe Big Prize (IOI17_prize)C++14
91.60 / 100
90 ms616 KiB
#include "prize.h" #include <iostream> #include <algorithm> #include <cmath> #include <ctime> #include <cstdlib> #include <vector> #include <unistd.h> #include <cassert> using namespace std; const int maxn=2e5+5; const int cap=1000; int sum; bool asked[maxn]; int uk; int nadji(int L, int D, int vall, int vald){ int mid=(L+D)/2; vector < int > v={-1, -1}; while(mid<D && v[0]+v[1]!=sum){ if(!asked[mid]){ uk++; v=ask(mid); asked[mid]=1; if(!v[0] && !v[1]){ return mid; } } mid++; } if(v[0]+v[1]!=sum){ mid=(L+D)/2; while(mid>=L && v[0]+v[1]!=sum){ if(!asked[mid]){ uk++; v=ask(mid); asked[mid]=1; if(!v[0] && !v[1]){ return mid; } } mid--; } if(v[0]+v[1]!=sum){ return -1; } uk--; mid++; } else{ uk--; mid--; } assert(uk<cap); int br=-1; if(v[0]-vall){ br=nadji(L, mid, vall, v[1]); if(br!=-1){ return br; } } if(v[1]-vald){ br=nadji(mid+1, D, v[0], vald); } return br; } int find_best(int n){ srand(time(NULL)*getpid()); vector < int > v; int pos; for(int i=0; i<1000; i++){ pos=rand()%n; v=ask(pos); if(!v[0] && !v[1]){ return pos; } sum=max(v[0]+v[1], sum); } int a=nadji(0, n, 0, 0); assert(a!=-1); return a; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...