# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
95223 | 2019-01-28T17:08:36 Z | MvC | The Big Prize (IOI17_prize) | C++11 | 0 ms | 0 KB |
#include "prize.h" #include<bits/stdc++.h> #include <vector> #include <algorithm> #include <set> using namespace std; int m, res; bool flag = false; vector<int> mem[200005]; vector<int> qr(int x){ if(mem[x].size() == 0) mem[x] = ask(x); return mem[x]; } void solve(int l, int r, int num, int bef){ if(num == 0) return; if(l > r) return; int mid = (l+r)/2; vector<int> resp = qr(mid); if(resp[0]+resp[1] == 0){ res = mid; flag = true; return; } int b = mid; while(resp[0]+resp[1] != m && b < r){ b++; resp = qr(b); if(resp[0]+resp[1] == 0){ res = b; flag = true; return; } } if(resp[0]+resp[1] == m){ solve(b+1, r, num-(resp[0]-bef), resp[0]); if(flag) return; solve(l, mid-1, resp[0]-(b-mid)-bef, bef); if(flag) return; } else{ solve(l, mid-1, num, bef); } return; } int find_best(int n) { srand(time(0)); if(n <= 5000){ for(int i=0; i<n; i++){ vector<int> resp = qr(i); if(resp[0]+resp[1] == 0) return i; } } vector<int> resp; set<int> s; vector<int>vc; set<int>ss; for(int i=0;i<n;i++)ss.insert(i); int x=0; for(x<600){ int i = rand()%n; if(ss.find(i)!=ss.end()) { x++; ss.erase(ss.find(i)); } else continue; resp = qr(i); if(resp[0]+resp[1] == 0) return i; s.insert(resp[0]+resp[1]); m = max(m, resp[0]+resp[1]); if(s.size() == 4) break; } solve(0, n-1, m, 0); return res; }