#include "prize.h"
#include <bits/stdc++.h>
using namespace std;
int find_best(int n) {
// 5 types!
vector<pair<int, int>> cache(n, { -1, -1 });
set<int> found;
int lolpop = 0;
for (int i = 0; i < min(n, 474) && lolpop <= 26; i++) {
auto j = ask(i);
cache[i] = { j[0], j[1] };
lolpop = max(lolpop, j[0] + j[1]);
if (j[0] + j[1] == 0) return i;
found.insert(i);
}
int crnt = 0;
while (crnt < n) {
auto qry = cache[crnt];
if (qry.first == -1) {
found.insert(crnt);
auto j = ask(crnt);
qry = { j[0], j[1] };
cache[crnt] = qry;
}
if (qry.first + qry.second == 0) return crnt;
if (qry.first + qry.second == lolpop) break;
crnt++;
}
while (crnt < n) {
auto crntval = cache[crnt];
if (crntval.first == -1) {
found.insert(crnt);
auto j = ask(crnt);
crntval = { j[0], j[1] };
cache[crnt] = crntval;
}
int low = crnt, high = n, ans = crnt;
for (int i : found) {
if (cache[i].second == crntval.second) {
low = max(low, i);
}
if (i > crnt && cache[i].second != crntval.second) {
high = min(high, i);
}
}
high--;
while (low <= high) {
int x = (low + high) / 2;
pair<int, int> qry = cache[x];
if (qry.first == -1) {
found.insert(x);
auto j = ask(x);
qry = { j[0], j[1] };
cache[x] = qry;
}
if (qry.first + qry.second == 0) return x;
if (qry.first == 0 && qry.second == 1) {
ans = x;
break;
}
if (qry.second != crntval.second) {
high = x - 1;
}
else {
low = x + 1;
ans = x;
}
}
crnt = ans + 1;
while (crnt < n) {
auto qry = cache[crnt];
if (qry.first == -1) {
found.insert(crnt);
auto j = ask(crnt);
qry = { j[0], j[1] };
cache[crnt] = qry;
}
if (qry.first + qry.second == 0) return crnt;
if (qry.first + qry.second == lolpop) break;
crnt++;
}
}
}
컴파일 시 표준 에러 (stderr) 메시지
prize.cpp: In function 'int find_best(int)':
prize.cpp:84:1: warning: control reaches end of non-void function [-Wreturn-type]
84 | }
| ^
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |