Submission #1045262

#TimeUsernameProblemLanguageResultExecution timeMemory
1045262beaconmcThe Big Prize (IOI17_prize)C++14
100 / 100
142 ms2892 KiB
#include "prize.h" #include <bits/stdc++.h> typedef int ll; #define FOR(i,x,y) for(ll i=x; i<y; i++) #define FORNEG(i,x,y) for(ll i=x; i>y; i--) using namespace std; map<ll, vector<ll>> cache; vector<ll> query(int n){ if (cache.count(n)) return cache[n]; else return cache[n] = ask(n); } int find_best(int n) { cache.clear(); vector<ll> stuff(n); vector<ll> newstuff(n); FOR(i,0,n) stuff[i] = i, newstuff[i] = i; ll maxi = -1; random_device rd; mt19937 g(rd()); shuffle(newstuff.begin(), newstuff.end(), g); FOR(i,0,min(455, n)){ vector<ll> sus = query(newstuff[i]); maxi = max(maxi, sus[0]+sus[1]); } vector<ll> found; ll ans = -1; while (ans == -1){ ll lo = 0; ll hi = stuff.size()-1; bool skip = false; while (lo < hi){ ll mid = (lo+hi)/2; ll cur = 1; while (cur < 10000){ if (lo <= mid-cur && cache.count(stuff[mid-cur])){ mid = mid-cur; break; } if (mid+cur < hi && cache.count(stuff[mid+cur])){ mid = mid+cur; break; } cur++; } vector<ll> sus = query(stuff[mid]); if (sus[0] + sus[1] < maxi){ if (sus[0]+sus[1]==0) return stuff[mid]; found.push_back(stuff[mid]); stuff.erase(stuff.begin()+mid); skip = true; break; }else{ sort(found.begin(), found.end()); ll idk = upper_bound(found.begin(), found.end(), stuff[mid]) - found.begin(); if (idk < sus[0]){ hi = mid; }else{ lo = mid+1; } } } if (skip) continue; vector<ll> sus = query(stuff[lo]); if (sus[0]+sus[1] == maxi) break; if (sus[0]+sus[1]==0) return stuff[lo]; found.push_back(stuff[lo]); stuff.erase(stuff.begin()+lo); } return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...