//#define LOCAL
#include "insects.h"
#include <algorithm>
#include<bits/stdc++.h>
using namespace std;
#define pb push_back
set<int> bucket;
void push_in(int insect){
assert(bucket.find(insect) == bucket.end());
bucket.insert(insect);
move_inside(insect);
}
void push_out(int insect){
assert(bucket.find(insect) != bucket.end());
bucket.erase(insect);
move_outside(insect);
}
void empty_bucket(){
for(int u:bucket){
push_out(u);
}
}
int min_cardinality(int N) {
srand(42);
bucket.clear();
int D = 0;
set<int> insect_q;
for(int i = 0 ; i < N ; i++){
push_in(i);
if(press_button() == 1){D++;}
else{insect_q.insert(i); push_out(i);}
}
//On va maintenant proceder a la dichotomie
int low = 1 ;
int high = N / D + 1;
while(high - low > 1){
vector<int> to_inspect;
for(int u:insect_q)to_inspect.emplace_back(u);
random_shuffle(to_inspect.begin(), to_inspect.end());
int bound = (low + high)/2;
vector<int> add_tturn, out;
for(int i:to_inspect){
push_in(i);
int r = press_button();
if(r > bound){
push_out(i);
out.push_back(i);
continue;
}
add_tturn.push_back(i);
if(bound*D == bucket.size())break;
}
if(bound*D==bucket.size()){
low = bound;
for(int u:add_tturn)insect_q.erase(u);
}else{
for(int u:add_tturn)push_out(u);
for(int u:out)insect_q.erase(u);
high = bound;
}
}
return low;
}
