#include "prize.h"
#include <map>
#include <random>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;
struct infos {
int pos, left, right;
infos(int pos_, int left_, int right_) : pos(pos_), left(left_), right(right_) {};
};
mt19937 mt(1902272037);
int rand_rng(int l, int r) {
uniform_int_distribution<int> p(l, r - 1);
return p(mt);
}
vector<int> random_pos(int n, int m) {
vector<int> ans;
for(int i = 0; i < m; ++i) {
int x = -1;
while(x == -1 || find(ans.begin(), ans.end(), x) != ans.end()) {
x = rand_rng(0, n);
}
ans.push_back(x);
}
sort(ans.begin(), ans.end());
return ans;
}
int find_best(int n) {
vector<int> samples = random_pos(n, min(n, 5));
int all = 0;
for(int i : samples) {
vector<int> res = ask(i);
all = max(all, res[0] + res[1]);
}
vector<infos> v = { infos(-1, 0, all), infos(n, all, 0) };
vector<int> s;
while(true) {
/*
for(infos i : v) {
cout << i.pos << ' ' << i.left << ' ' << i.right << endl;
}
* */
int maxd = 0, ptr = -1, mrem = -1;
for(int i = 0; i < int(v.size()) - 1; ++i) {
int rem = v[i].right + v[i + 1].left - all;
rem -= lower_bound(s.begin(), s.end(), v[i + 1].pos) - lower_bound(s.begin(), s.end(), v[i].pos);
if(rem > 0 && v[i + 1].pos - v[i].pos > maxd) {
maxd = v[i + 1].pos - v[i].pos;
ptr = i;
mrem = rem;
}
}
//cout << "* " << ptr << ' ' << maxd << ' ' << mrem << endl;
//cout << "*";
//for(int i : s) cout << ' ' << i; cout << endl;
if(ptr == -1) break;
if(maxd >= 2) {
int pl = v[ptr].pos, pr = v[ptr + 1].pos;
int m = (pl + pr) / 2;
vector<int> res = ask(m);
if(res[0] + res[1] == 0) return m;
if(res[0] + res[1] == all) {
v.insert(v.begin() + ptr + 1, infos(m, res[0], res[1]));
}
else {
--mrem;
s.push_back(m);
int cm = m - 1, flag = 0;
while(mrem > 0 && cm > pl) {
vector<int> res2 = ask(cm);
if(res2[0] + res2[1] == 0) return cm;
if(res2[0] + res2[1] == all) {
v.insert(v.begin() + ptr + 1, infos(cm, res2[0], res2[1]));
flag = 1;
break;
}
s.push_back(cm);
--mrem;
--cm;
}
cm = m + 1;
while(mrem > 0 && cm < pr) {
vector<int> res2 = ask(cm);
if(res2[0] + res2[1] == 0) return cm;
if(res2[0] + res2[1] == all) {
v.insert(v.begin() + ptr + 1 + flag, infos(cm, res2[0], res2[1]));
break;
}
s.push_back(cm);
--mrem;
++cm;
}
sort(s.begin(), s.end());
}
}
}
return -1;
}
