# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
390540 | aarr | 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 "prize.h"
#include <bits/stdc++.h>
using namespace std;
int n;
const int N = 200 * 1000 + 5;
pair <int, int> res[N];
bool mark[N];
int solve(int s, int e) {
if (e - s <= 2) {
return n;
}
int md = (s + e) / 2;
ask_save(md);
if (res[md].first + res[md].second == 0) {
return md;
}
int ans = n;
if (res[md] != res[s]) {
ans = solve(s, md + 1);
if (ans < n) {
return ans;
}
}
if (res[md] != res[e]) {
ans = min(ans, solve(md, e));
}
return ans;
}
int find_best(int n) {
ask_save(0);
ask_save(n - 1);
if (res[0].first + res[0].second == 0) {
return 0;
}
if (res[n - 1].first + res[n - 1].second == 0) {
return n - 1;
}
return solve(0, n);
}