#include <bits/stdc++.h>
#include "insects.h"
using namespace std;
int min_cardinality(int N) {
int cnt=0;
set<int> in;
vector<int> ids;
for(int i=0;i<N;i++){
ids.push_back(i);
move_inside(i);
int x=press_button();
if(x>1)move_outside(i);
else{
cnt++;
in.insert(i);
}
}
if(cnt==1)return N;
int l=1,r=N/cnt;
std::random_device rd;
std::mt19937 g(rd());
std::shuffle(ids.begin(), ids.end(), g);
while(l<r){
int mid=(l+r+1)/2;
if(r-l>=4)mid=l+(r-l)/4;
for(int id=0;id<N;id++){
int i=ids[id];
if(in.size()==mid*cnt || in.find(i)!=in.end())continue;
move_inside(i);
int x=press_button();
if(x>mid)move_outside(i);
else in.insert(i);
}
if(in.size()==mid*cnt)l=mid;
else{
r=mid-1;
for(auto i:in)move_outside(i);
in.clear();
}
}
return l;
}
