| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1197253 | sirius | The Big Prize (IOI17_prize) | C++20 | 0 ms | 0 KiB |
#include <bits/stdc++.h>
using namespace std;
int find_best(int n) {
const int SAMPLE_SIZE = 500;
map<int, vector<int>> sum_to_indices;
vector<pair<int, int>> responses(n, {-1, -1});
for (int i = 0; i < min(n, SAMPLE_SIZE); ++i) {
vector<int> res = ask(i);
responses[i] = {res[0], res[1]};
int sum = res[0] + res[1];
if (sum == 0) return i;
sum_to_indices[sum].push_back(i);
}
function<int(int, int)> search = [&](int left, int right) -> int {
if (left > right) return -1;
for (const auto& [sum, indices] : sum_to_indices) {
for (int i = 0; i < indices.size(); ++i) {
for (int j = i + 1; j < indices.size(); ++j) {
int idx1 = indices[i], idx2 = indices[j];
if (idx1 < left && idx2 > right) {
int x = responses[idx1].first;
int y = responses[idx2].first;
int count_between = y - x;
int known_between = 0;
for (int k = idx1 + 1; k < idx2; ++k) {
if (responses[k].first != -1) {
if (responses[k].first + responses[k].second < sum)
++known_between;
}
}
if (count_between == known_between)
return -1;
}
}
}
}
int mid = (left + right) / 2;
if (responses[mid].first == -1) {
vector<int> res = ask(mid);
responses[mid] = {res[0], res[1]};
int sum = res[0] + res[1];
if (sum == 0) return mid;
sum_to_indices[sum].push_back(mid);
}
int res_left = search(left, mid - 1);
if (res_left != -1) return res_left;
return search(mid + 1, right);
};
return search(0, n - 1);
}