# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
1214566 | exoworldgd | The Big Prize (IOI17_prize) | C++20 | 0 ms | 0 KiB |
#include <bits/stdc++.h>
using namespace std;
map<int,vector<int>> mp;
vector<int> q(int idx) {
if (mp.find(idx) != mp.end()) return mp[pos];
vector<int> res = ask(pos);
mp[pos] = res;
return res;
}
int find_best(int n) {
mp.clear();
int l = 0, r = n-1;
while (l <= r) {
int m = l+(r-l)/2;
vector<int> res = q(m);
int ll = res[0], rr = res[1];
if (ll+rr == n-1) return m;
if (ll>rr) r = m-1;
else l = m+1;
}
for (int i = 0; i < n; i++) {
vector<int> res = query(i);
if (res[0]+res[1] == n-1) return i;
}
return 0;
}