Submission #976966

#TimeUsernameProblemLanguageResultExecution timeMemory
976966Error404The Big Prize (IOI17_prize)C++17
20 / 100
960 ms1048576 KiB
#include "prize.h" #include <bits/stdc++.h> using namespace std; #define pi pair<int,int> #define f first #define s second const int MAX_N = 2e5; int ans[MAX_N][2]; bool found = false; int pos; int last ; pi q(int l){ if(ans[l][0]!=-1) return {ans[l][0], ans[l][1]}; else{ auto hold = ask(l); ans[l][0] =hold[0]; ans[l][1] =hold[1]; return {ans[l][0], ans[l][1]}; // return {0,1}; } } void solve( int l, int r ) { if(found) return; if(l>r) return; int m = (l+r)/2; pi res = q(m); if(res.f ==0 && res.s==0){ pos = m; found = true; return; } if(res.f<res.s){ if(res.f!=0){ solve(l,min(m,last-1)); } if(res.s!=0){ solve(max(0,m+1),r); } } else{ if(res.f!=0){ solve(l,min(m,last-1)); } if(res.s!=0){ solve(max(0,m+1),r); } } } int find_best( int n ) { for( int i = 0; i < n; i++ ) ans[i][0] = ans[i][1] = -1; last = n-1; solve( 0, n - 1 ); return pos; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...