Submission #222752

#TimeUsernameProblemLanguageResultExecution timeMemory
222752achibasadzishviliThe Big Prize (IOI17_prize)C++14
90 / 100
85 ms2744 KiB
#include<bits/stdc++.h> #define ll int #define f first #define s second #define pb push_back #include "prize.h" using namespace std; pair<ll,ll>p , cur , pp[200005]; ll que,fix[200005] , mx , tt = 0; set<ll>st; set<ll>::iterator it; pair<ll,ll> as(ll ind){ if(fix[ind])return pp[ind]; fix[ind] = 1; vector<ll>v = ask(ind); que++; pp[ind] = make_pair(v[0] , v[1]); if(v[0] + v[1] != mx && tt == 1){ st.insert(ind); } return pp[ind]; } ll find_best(ll n){ srand(time(NULL)); ll ind = 0; mx = 0; vector<ll>ff; for(int i=1; i<=500; i++){ ll t = rand() % n; p = as(t); ff.pb(t); if(p.f + p.s > mx){ mx = p.f + p.s; ind = t; } } tt = 1; ll x = ind; st.insert(0); st.insert(n - 1); for(int i=0; i<ff.size(); i++) if(pp[ff[i]].f + pp[ff[i]].s != mx) st.insert(ff[i]); while(x < n){ p = as(x); cur = p; if(p.f + p.s == mx){ ll l = x + 1 , r = n - 1 , mid , nex = x; if(st.upper_bound(x) != st.end()) r = (*st.upper_bound(x)); while(r >= l){ mid = (l + r) / 2; p = as(mid); if(p.s == cur.s){ l = mid + 1; nex = mid; } else { r = mid - 1; } } x = nex + 1; } else { if(p.f + p.s == 0)return x; x++; } } x = ind; while(x >= 0){ p = as(x); cur = p; if(p.f + p.s == mx){ it = st.lower_bound(x); it--; ll l = (*it) , r = x - 1 , mid , nex = x; while(r >= l){ mid = (l + r) / 2; p = as(mid); if(p.f == cur.f){ r = mid - 1; nex = mid; } else { l = mid + 1; } } x = nex - 1; } else { if(p.f + p.s == 0)return x; x--; } } return 0; }

Compilation message (stderr)

prize.cpp: In function 'int find_best(int)':
prize.cpp:40:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0; i<ff.size(); i++)
                  ~^~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...