// moreflags=grader.cpp
// 11
// :(
#include "prize.h"
#if not LOCAL
#define NDEBUG
#endif
#include<vector>
#include<algorithm>
#include<cassert>
std::vector<std::vector<int>> result;
int find_best(int const n) {
/*
if(n<=5000){
for(int i = 0; ; i++) {
assert(i<n);
std::vector<int> res = ask(i);
if(res[0] + res[1] == 0)
return i;
}
}
assert(n>5000);
*/
result.clear(); result.resize(n);
auto const ask=[&](int pos)->void{
if(result[pos].empty())
result[pos]=::ask(pos);
};
int maxTotal{};
for(int index=0; index<473; ++index){
auto const pos=n*index/473;
ask(pos);
maxTotal=std::max(maxTotal, result[pos][0]+result[pos][1]);
}
// so far 473 questions asked
auto const isLollipop=[&](int pos){
return result[pos][0]+result[pos][1]==maxTotal;
};
for(int index=0; index<473; ++index){
auto left=n*index/473, right=n*(index+1)/473;
assert(not result[left].empty());
assert(right==n or not result[right].empty());
while(left+1<right and not isLollipop(left)) ask(++left);
}
// 473+x questions asked, x non-lollipops found
auto const process=[&](auto process, int left, int right, int countRight, int delta){
// given delta non-lollipops in (left..right), ask them all in k*delta questions
// with right-left<=2**k-1
// countRight=number of non-lollipops in (left..)
if(delta==0) return;
assert(delta>0);
assert(countRight>=delta);
assert(left<right);
auto const middle=(left+right)>>1;
ask(middle);
int pos=middle;
while(not isLollipop(pos)){
++pos;
if(pos==right) break;
ask(pos);
}
auto const deltaMid=pos-middle;
if(pos==right){
for(int pos=middle; pos<right; ++pos) assert(not isLollipop(pos));
process(process, left, middle, countRight, delta-deltaMid);
}else{
auto const countRight1=result[pos][1];
auto const deltaLeft=countRight-countRight1-deltaMid;
process(process, left, middle, countRight, deltaLeft);
process(process, pos+1, right, result[pos][1], delta-deltaLeft-deltaMid);
}
};
auto const cutCondition=[&](int pos){
return pos==n or (not result[pos].empty() and isLollipop(pos));
};
for(int pos=0; pos<n; ++pos) if(cutCondition(pos)){
int next=pos+1; while(not cutCondition(next)) ++next;
int right=next;
while(pos+1<right and not result[right-1].empty()){
assert(not isLollipop(right-1));
--right;
}
if(pos+1==right) continue;
assert(std::all_of(result.begin()+pos+1, result.begin()+right, [&](auto const& it){
return it.empty();}));
for(int pos=right; pos<next; ++pos)
assert(not isLollipop(pos));
assert(isLollipop(pos)); assert(next==n or isLollipop(next));
int const delta=result[pos][1]-(next==n ? 0: result[next][1]);
process(process, pos+1, right, result[pos][1], delta-(next-right));
}
// all non-lollipops found
for(int pos=0;; ++pos) if(not result[pos].empty() and result[pos][0]==0 and result[pos][1]==0)
return pos;
}
