#include <iostream>
#include <vector>
#include <set>
#include <map>
#include "prize.h"
#include <random>
using namespace std;
std::default_random_engine generator;
set<int> seen;
typedef pair<int,int> pii;
struct Info {
int lefthighercount = 0;
int righthighercount = 0;
};
typedef map<int, Info> Level;
map<int, Level> levels;
void debug() {
cerr << "Seen: ";
for (int x: seen) cerr << x << " ";
cerr << endl;
cerr << "Levels: " << endl;
for (auto& s: levels) {
cerr << "v=" << s.first << ": ";
for (auto& p: s.second) {
cerr << p.first << "(" << p.second.lefthighercount << ","
<< p.second.righthighercount << ") ";
}
cerr << endl;
}
cerr << endl;
}
int count(int a, int b) {
auto itfrom = seen.lower_bound(a);
auto itto = seen.lower_bound(b);
int num=0;
while (itfrom != itto) {
++num;
++itfrom;
}
return num;
}
// Randomly find some interval in level within [ca,cb) that
// is a good candidate to query.
pii findinterval(int ca, int cb, const Level& l) {
auto it = l.upper_bound(ca);
--it;
// cerr << "Level" << endl;
vector<pii> candidates;
while(it->first + 1 < cb) {
int a = it->first + 1;
int lefta = it->second.lefthighercount;
++it;
int b = it->first;
int leftb = it->second.lefthighercount;
if (a == b) continue;
// int l = b - a; // #spots
// l -= count(seen, a, b); // l = #empty spots
int goodones = leftb - lefta;
// cerr << "[" << a << "," << b << "): " << goodones << " goodones" << endl;
if (goodones > 0 && (count(a, b) < b - a)) {
candidates.push_back({a, b});
}
}
if (candidates.size() == 0) {
return {-1, -1};
}
uniform_int_distribution<int> distribution(0, candidates.size()-1);
auto p = candidates[distribution(generator)];
return {max(p.first, ca), min(p.second, cb)};
}
int find_best(int n) {
while (1) {
// debug();
// cerr << "XXX" << endl;
int a = 0, b = n;
if (!seen.empty()) {
do {
a = 0, b = n;
for (auto it = levels.begin(); it != levels.end(); ++it) {
tie(a, b) = findinterval(a, b, it->second);
// cerr << "Level " << it->first << ": [" << a << "," << b << ")"
// << endl;
if (a == -1 && b == -1) break;
}
// cerr << "." << endl;
} while (a == -1 && b == -1);
}
// find best spot in [a, b)
int m = (a+b)/2;
int next = 1;
int signnext = 1;
// cerr << "Checking " << m << "..." << endl;
while (m < a || m >= b || seen.find(m) != seen.end()) {
m += signnext * next;
++next;
signnext *= -1;
//cerr << "Taken. Checking " << m << "..." << endl;
}
auto q = ask(m);
seen.insert(m);
int v = q[0]+q[1];
if (v == 0) return m;
auto& s = levels[v];
if (s.empty()) {
s[-1] = Info{0, q[0]+q[1]};
s[n] = Info{q[0]+q[1], 0};
}
s[m] = Info{q[0], q[1]};
}
}
// int find_best(int n) {
// int m = n/2;
// auto q = ask(m);
// seen.insert(m);
// int v = q[0]+q[1];
// if (v == 0) return m;
// {
// auto& s = intervals[v];
// s[-1] = Info{0, q[0]+q[1]};
// s[m] = Info{q[0], q[1]};
// s[n] = Info{q[0]+q[1], 0};
// }
// while (1) {
// debug();
// auto its = intervals.end();
// --its;
// auto& s = its->second;
// double bestscore = 0;
// auto bestit = s.end();
// for (auto it = s.begin(); it->first != n;) {
// int a = it->first + 1;
// int lefta = it->second.lefthighercount;
// ++it;
// int b = it->first;
// int leftb = it->second.lefthighercount;
// int l = b - a; // #spots
// l -= count(seen, a, b); // l = #empty spots
// cerr << "[" << a << "," << b << "): " << l << " empty ";
// int goodones = leftb - lefta;
// cerr << goodones << " goodones" << endl;
// if (l > 0 || goodones > 0) {
// if (goodones > 0) {
// double score = ((double)goodones)/(l+1);
// if (score > bestscore) {
// bestit = it;
// bestscore = score;
// cerr << "bestscore: " << bestscore << endl;
// }
// }
// }
// }
// // find best spot in [ita, itb)
// auto ita = bestit, itb = bestit;
// --ita;
// int a = ita->first+1;
// int b = itb->first;
// int m = (a+b)/2;
// int next = 1;
// int signnext = 1;
// while (m < a || m >= b || seen.find(m) != seen.end()) {
// m += signnext * next;
// ++next;
// signnext *= -1;
// }
// auto q = ask(m);
// seen.insert(m);
// int v = q[0]+q[1];
// if (v == 0) return m;
// auto& s2 = intervals[v];
// if (s2.empty()) {
// s2[-1] = Info{0, q[0]+q[1]};
// s2[n] = Info{q[0]+q[1], 0};
// }
// s2[m] = Info{q[0], q[1]};
// }
// }
// int find_best(int n) {
// if (segments.empty()) {
// int m = n/2;
// auto q = ask(m);
// int v = q[0]+q[1];
// if (v == 0) return m;
// segments[v][{0, m}] = Info{q[0], 0, q[1]};
// segments[v][{m+1, n}] = Info{q[1], q[0], 0};
// }
// while (1) {
// auto its = segments.end();
// --its;
// auto& s = its->second;
// double bestp = 0;
// auto bestit = s.end();
// for (auto it = s.begin(); it != s.end(); ++it) {
// int l = it->first.second - it->first.first;
// if (l > 0) {
// double p = ((double)it->second.higher)/l;
// if (p>bestp) {
// bestit = it;
// bestp = p;
// }
// }
// }
// auto x = bestit->first;
// auto oldinfo = bestit->second;
// int m = (x.first+x.second)/2;
// auto q = ask(m);
// int v = q[0] + q[1];
// if (v == 0) return m;
// // fix here, different v.
// s.erase(bestit);
// s[{x.first, m}] = Info{q[0]-oldinfo.leftsum, oldinfo.leftsum, q[1]};
// s[{m+1, x.second}] = Info{q[1]-oldinfo.rightsum, q[0], oldinfo.rightsum};
// }
// return -1;
// }
