Submission #122595

#TimeUsernameProblemLanguageResultExecution timeMemory
122595tselmegkhThe Big Prize (IOI17_prize)C++14
100 / 100
64 ms10328 KiB
#include<bits/stdc++.h> #include "prize.h" using namespace std; #define INF 1e9 #define MAX 200005 #define xx first #define yy second #define pb push_back #define mp make_pair #define ull long long #define FOR(i,a,b) for(int i=a;i<=b;i++) #define nl '\n' #define zai <<' '<< #define all(a) a.begin(),a.end() #define pc __builtin_popcount #define debug(args...) cerr << #args << " = "; Dbg,args; cerr << nl; struct Dbg { template<typename T> Dbg& operator,(const T& v) { cerr << v << ", "; return *this; } } Dbg; template <typename T> ostream& operator<<(ostream& _o_, const vector<T>& _v_){ if(!_v_.empty()){_o_<<'[';copy(_v_.begin(),_v_.end(),ostream_iterator<T>(_o_,", "));_o_<<"\b\b]";}return _o_;} typedef vector<int> vi; typedef pair<int,int> ii; typedef vector<ii> vii; template<class C> void mini(C &_a, C _b) { _a = min(_a, _b); } template<class C> void maxi(C &_a, C _b) { _a = max(_a, _b); } map<int, vi> mymap[MAX]; int res = -1; void go(int l, int r){ if(l > r)return; if(res != -1)return; int mid = (l + r) >> 1; vi query = ask(mid); if(query[0] + query[1] == 0){ res = mid; return; } bool ansonl = 1, ansonr = 1; auto uit = mymap[query[0] + query[1]].upper_bound(mid); if(uit != mymap[query[0] + query[1]].end()){ if((*uit).second[0] == query[0])ansonr = 0; } if(uit != mymap[query[0] + query[1]].begin()){ uit--; } if(uit != mymap[query[0] + query[1]].begin()){ if((*uit).second[1] == query[1])ansonl = 0; } mymap[query[0] + query[1]][mid] = query; if(ansonr){ go(mid + 1, r); } if(ansonl){ go(l, mid - 1); } } int find_best(int n){ go(0, n - 1); return res; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...