# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
1157394 | vjudge3 | The Big Prize (IOI17_prize) | C++20 | 0 ms | 0 KiB |
#include <bits/stdc++.h>
using namespace std;
vector<int> ask(int i);
int candidate_cnt;
int query(int l, int r, int cnt, int lcnt, int rcnt) {
if (l > r || !cnt) return -1;
int mid = (l+r)/2;
vector<int> res = ask(mid);
if (res[0]+res[1] == 0) return mid;
if (res[0]+res[1] == candidate_cnt) return max(query(l, mid, cnt - (res[1]-rcnt), lcnt, res[1]), query(mid, r, cnt - (res[0]-lcnt), res[0], rcnt));
int midl = mid-1, midr = mid+1;
vector<int> lres, rres;
for (; midl >= l; midl--) {
lres = ask(midl);
if (lres[0]+lres[1] == 0) return midl;
if (lres[0]+lres[1] == candidate_cnt) break;
}
for (; midr <= r; midr++) {
rres = ask(midr);
if (rres[0]+rres[1] == 0) return midr;
if (rres[0]+rres[1] == candidate_cnt) break;
}
return max(query(l, midl, cnt - (lres[1]-rcnt), lcnt, lres[1]), query(midr, r, cnt - (rres[0]-lcnt), rres[0], rcnt));
}