#include <bits/stdc++.h>
#include "insects.h"
using namespace std;
// determine no. of groups and 1st insect in each grp - around n cost
// with m groups the answer is at most n/m
// repeat but remove the 1st in each group to find the 2nd in each group
// this method lets us find the size of smallest grp in O(smallest grp size * n) = O(n^2/m)
// alternatively, find the elements of the largest grp in O(n), repeat for every group = O(nm)
// small/large split gives O(nsqrtn)
int min_cardinality(int N) {
int d = 0;
bool marked[N]; memset(marked,false,sizeof(marked));
vector<int> to_remove;
for(int i=0;i<N;i++) {
move_inside(i);
int res = press_button();
if(res>1) {
move_outside(i);
}
else {
d++;
marked[i]=true;
to_remove.push_back(i);
}
}
for(int x: to_remove) move_outside(x);
int ans = 0;
int lo=1,hi=N/d;
while(lo<=hi) {
int mid = (lo+hi)/2;
to_remove.clear();
int cnt=0;
for(int i=0;i<N;i++) {
move_inside(i);
int res = press_button();
if(res > mid) {
move_outside(i);
}
else {
cnt++;
to_remove.push_back(i);
}
}
if(cnt==d*mid) {
lo=mid+1;
ans=max(ans,mid);
}
else {
hi=mid-1;
}
}
return ans;
}
