| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 316305 | nikatamliani | The Big Prize (IOI17_prize) | C++14 | 0 ms | 0 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 <bits/stdc++.h>
using namespace std;
#include "prize.h"
vector < vector < int > > memo;
vector < int > memo_ask(int x) {
if(!memo[x].empty()) return memo[x];
return memo[x] = ask(x);
}
int find_best(int n) {
if(n < 5000) {
for(int i = 0; i < n; ++i) if(memo_ask(i)[0] + memo_ask(i)[1] == 0) return i;
}
int next = -1, at_most = 500;
vector < int > bad(2);
memo.resize(n);
for(int i = 0; i <= at_most; ++i) {
if(bad[0] + bad[1] < memo_ask(i)[0] + memo_ask(i)[1]) {
bad = memo_ask(i);
}
if(memo_ask(i)[0] == 0 && memo_ask(i)[1] == 0) return i;
}
map < int, int > f;
for(int i = 0; i <= at_most; ++i) {
if(bad[0] + bad[1] != memo_ask(i)[0] + memo_ask(i)[1]) {
if(second_bad[0] + second_bad[1] < memo_ask(i)[0] + memo_ask(i)[1]) {
second_bad = memo_ask(i);
}
}
++f[memo_ask(i)[0] + memo_ask(i)[1]];
}
int min_sum = 1e9, count_more = 0;
for(auto [key, value] : f) {
if(value >= 26) {
min_sum = key;
++count_more;
break;
}
}
assert(count_more > 1);
const int BLOCK_SIZE = 1000;
for(int i = at_most + 1; i < n; i = next + 1) {
int l = i, r = n - 1; next = -1;
vector < int > t = memo_ask(i);
if(t[0] + t[1] < min_sum) {
next = i;
if(t[0] == 0 && t[1] == 0) return i;
continue;
}
int maybe = i + BLOCK_SIZE;
if(maybe < n && memo_ask(maybe)[0] + memo_ask(maybe)[1] >= min_sum) {
next = maybe;
continue;
}
if(maybe < n) r = maybe - 1;
while(r >= l) {
int m = l + r >> 1;
if(memo_ask(m)[0] + memo_ask(m)[1]) {
next = m;
l = m + 1;
} else {
r = m - 1;
}
}
}
}