Submission #622996

#TimeUsernameProblemLanguageResultExecution timeMemory
622996AbdelmagedNourThe Big Prize (IOI17_prize)C++17
100 / 100
54 ms5436 KiB
#include<bits/stdc++.h> using namespace std; #include "prize.h" //#include "grader.cpp" int res=-1; vector<vector<int>>v; map<vector<int>,set<int>>mp; void divide(int l,int r){ if(l>r||res!=-1)return; if(l==r){ v[l]=ask(l); mp[v[l]].insert(l); if(v[l][0]+v[l][1]==0)res=l; return; } int md=(l+r)>>1; if(v[md].size()==0)v[md]=ask(md); if(v[md][0]+v[md][1]==0)res=md; mp[v[md]].insert(md); if(!(mp[v[md]].size()&&*(mp[v[md]].begin())<md)&&v[md][0])divide(l,md-1); if(!(mp[v[md]].size()&&*(mp[v[md]].rbegin())>md)&&v[md][1])divide(md+1,r); } int find_best(int n){ v.clear(); v.resize(n); mp.clear(); res=-1; v[0]=ask(0); v[n-1]=ask(n-1); mp[v[0]].insert(0); mp[v[n-1]].insert(n-1); if(v[0][0]+v[0][1]==0)return 0; if(v[n-1][0]+v[n-1][1]==0)return n-1; divide(1,n-2); return res; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...