| # | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 767789 | 2023-06-27T07:31:51 Z | SanguineChameleon | Simurgh (IOI17_simurgh) | C++17 | 0 ms | 0 KB |
#include "prize.h"
#include <bits/stdc++.h>
using namespace std;
const int maxn = 2e5 + 20;
const int lim = 474;
const int jump = 256;
vector<int> memo[maxn];
vector<int> get(int i) {
if (memo[i].empty()) {
memo[i] = ask(i);
}
return memo[i];
}
int find_best(int n) {
if (n <= lim) {
for (int i = 0; i < n; i++) {
vector<int> res = get(i);
if (res[0] + res[1] == 0) {
return i;
}
}
}
int mx = 0;
for (int i = 0; i < lim; i++) {
vector<int> res = get(i);
if (res[0] + res[1] == 0) {
return i;
}
mx = max(mx, res[0] + res[1]);
}
int cur = lim;
while (true) {
vector<int> res1 = get(cur);
if (res1[0] + res1[1] == 0) {
return cur;
}
if (res1[0] + res1[1] < mx) {
cur++;
continue;
}
if (cur + jump < n) {
vector<int> res2 = get(cur + jump);
if ((res2[0] + res2[1] == res1[0] + res1[1]) && (res2[0] == res1[0])) {
cur += jump;
continue;
}
}
int lt = cur + 1;
int rt = min(cur + jump - 1, n - 1);
while (lt <= rt) {
int mt = (lt + rt) / 2;
vector<int> res2 = get(mt);
if (res2[0] + res2[1] == 0) {
return mt;
}
if ((res2[0] + res2[1] == res1[0] + res1[1]) && (res2[0] == res1[0])) {
cur = mt;
lt = mt + 1;
}
else {
rt = mt - 1;
}
}
cur++;
}
return -1;
}