This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include "prize.h"
#include <bits/stdc++.h>
using namespace std;
const int N = 200200;
const int B = 450;
vector<int> arr[N];
vector<int> ASK(int p) {
if (arr[p].empty())
arr[p] = ask(p);
return arr[p];
}
int sum(int i) {
return ASK(i)[0] + ASK(i)[1];
}
int find_best(int n) {
int val = sum(0);
for (int i = 0; i < min(n, B); i++) {
if (!sum(i)) return i;
val = max(val, sum(i));
}
int cnt = 0;
for (int i = 0; i < B; i++)
cnt += (sum(i) < val);
for (int it = B; it < n; it += B) {
int rb = min(it + B - 1, n - 1), k = 0;
if (sum(rb) == val && arr[rb][0] == cnt)
continue;
while (rb >= it && sum(rb) < val) {
if (!sum(rb)) return rb;
k++;
rb--;
}
int i = it, del = arr[rb][0] - cnt;
while (i < rb && del) {
while (i < rb && sum(i) < val) {
if (!sum(i))
return i;
i++;
del--;
k++;
}
if (!del) break;
int l = i, r = rb;
while (r - l > 1) {
int mid = (l + r) / 2;
if (ASK(mid) == ASK(i))
l = mid;
else {
if (!sum(mid))
return mid;
r = mid;
}
}
i = r;
}
cnt += k;
}
return 0;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |