#include "prize.h"
using namespace std;
#include <bits/stdc++.h>
int non_worst_box_cnt = 0;
bool notworst(vector<int> res) {
return (res[0] + res[1] != non_worst_box_cnt);
}
bool best(vector<int> res) {
return (res[0] + res[1] == 0);
}
bool contains(int a, vector<int> ares, int b, vector<int> bres) {
//cout << " checking between " << a << " and " << b << "\n";
return bres[0] != ares[0];
}
vector<vector<int>> askcache(200000);
vector<bool> asked(200000);
vector<int> ask_(int i) {
//cout << "asking " << i << "\n";
if (!asked[i]) {
asked[i] = true;
askcache[i] = ask(i);
}
return askcache[i];
}
int binary_search(int min, int max) {
if (min > max) return -1;
if (min == max) {
if (best(ask_(min))) return min;
return -1;
}
int mid = (min + max) / 2;
auto minres = ask_(min);
if (notworst(minres)) {
if (best(minres)) {
return min;
}
return binary_search(min + 1, max);
}
auto maxres = ask_(max);
if (notworst(maxres)) {
if (best(maxres)) {
return max;
}
return binary_search(min, max - 1);
}
auto midres = ask_(mid);
if (notworst(midres)) {
if (best(midres)) {
return mid;
}
if (min + 4 < max)
return std::max(binary_search(min, mid), binary_search(mid, max));
else
return std::max(binary_search(min, mid), binary_search(mid + 1, max));
}
int opt = -1;
if (contains(min, minres, mid, midres)) {
opt = std::max(opt, binary_search(min, mid));
}
if (contains(mid, midres, max, maxres)) {
if (min + 4 < max)
opt = std::max(opt, binary_search(mid, max));
else
opt = std::max(opt, binary_search(mid + 1, max));
}
return opt;
}
int find_best(int n) {
for (int i = 0; i < 480 && i < n; i++) {
auto v = ask_(i);
if (best(v)) return i;
int va = v[0];
int vb = v[1];
non_worst_box_cnt = max(non_worst_box_cnt, va + vb);
}
return binary_search(0, n - 1);
}
