#include "insects.h"
#include <bits/stdc++.h>
using namespace std;
vector<int> perm;
void mi(int i){
move_inside(perm[i]);
}
void mo(int i){
move_outside(perm[i]);
}
int min_cardinality(int N) {
default_random_engine dre(time(NULL));
perm.resize(N);
iota(perm.begin(), perm.end(), 0);
shuffle(perm.begin(), perm.end(), dre);
set<int> specials;
specials.insert(0);
mi(0);
for(int i = 1; i < N; i++){
mi(i);
if(press_button() == 2){
mo(i);
}else{
specials.insert(i);
}
}
for(int i : specials) mo(i);
// 2 cases: #t <= sqrt(N) or #t > sqrt(N)
if(specials.size() * specials.size() <= 1.4 * N){
// case 1: use N log2 #t approach using pbsearch
vector<tuple<int,int,int>> pbs;
int c = -1;
for(int i = 0; i < N; i++){
if(specials.count(i) == 0) pbs.push_back({i, 0, c});
else c++;
}
vector<int> svec(specials.begin(), specials.end());
int ptr = -1;
while(true){
bool cont = false;
for(auto p : pbs){
if(get<1>(p) != get<2>(p)) cont = true;
}
if(!cont) break;
sort(pbs.begin(), pbs.end(), [](tuple<int,int,int> x, tuple<int,int,int> y){
return (get<1>(x) + get<2>(x)) / 2 < (get<1>(y) + get<2>(y)) / 2;
});
while(ptr > (get<1>(pbs.front()) + get<2>(pbs.front())) / 2){
mo(svec[ptr]);
ptr--;
}
vector<tuple<int,int,int>> npbs;
for(auto p : pbs){
if(get<1>(p) == get<2>(p)){
npbs.push_back(p);
continue;
}
int mid = (get<1>(p) + get<2>(p)) / 2;
for(int i = ptr+1; i <= mid; i++) mi(svec[i]);
ptr = mid;
mi(get<0>(p));
if(press_button() == 2){
// hi = mid
npbs.push_back({get<0>(p), get<1>(p), mid});
}else{
// lo = mid+1
npbs.push_back({get<0>(p), mid+1, get<2>(p)});
}
mo(get<0>(p));
}
pbs = npbs;
}
map<int,int> cards;
for(int x : specials) cards[x] = 1;
for(auto p : pbs) cards[svec[get<1>(p)]]++;
int mn = 5000;
for(auto x : cards) mn = min(mn, x.second);
return mn;
}else{
// case 2: use N log2 ans approach using bsearch on ans
int lo = 1;
int hi = N / specials.size();
int mid;
while(lo < hi){
mid = (lo + hi)/2;
set<int> machine;
for(int i = 0; i < N; i++){
if(specials.count(i) == 0){
mi(i);
machine.insert(i);
if(press_button() > mid){
machine.erase(i);
mo(i);
}
}
}
bool ok = false;
vector<int> svec(specials.begin(), specials.end());
shuffle(svec.begin(), svec.end(), dre);
for(int x : svec){
mi(x);
machine.insert(x);
if(press_button() == mid){
ok = true;
break;
}
mo(x);
machine.erase(x);
}
for(int x : machine){
mo(x);
}
if(ok){
hi = mid;
}else{
lo = mid+1;
}
}
return lo;
}
}
