# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
828680 | gromperen | The Big Prize (IOI17_prize) | C++14 | 79 ms | 11360 KiB |
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 MAXN = 2e5+5;
vector<vector<int>> memo(MAXN, vector<int>(2, -1));
vector<int> _ask(int i) {
if (memo[i][0] != -1) return memo[i];
return memo[i] = ask(i);
}
int find_best(int n) {
int mx = 0;
int sqrtn = sqrt(n);
int k = 0;
for(int i = 0; i < sqrtn; i++) {
vector<int> res = _ask(i);
if(res[0] + res[1] == 0) return i;
mx = max(mx, res[0] + res[1]);
}
for (int i = sqrtn; i < n; ++i) {
auto res = _ask(i);
if (res[0] + res[1] < mx) {
if (res[0] + res[1] == 0) return i;
continue;
}
int l = i, r = n-1;
int tmp = i;
while(l<r) {
int mid = (l+r)/2;
auto rmid = _ask(mid);
if (rmid[0]+rmid[1] < mx || rmid[1] < res[1]) {
if (rmid[0]+rmid[1] == 0) return mid;
r = mid-1;
} else {
l = mid+1;
tmp = mid;
}
}
i = tmp;
}
return 0;
}
Compilation message (stderr)
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |