#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 m = 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 {
m++;
marked[i]=true;
to_remove.push_back(i);
}
}
for(int x: to_remove) move_outside(x);
to_remove.clear();
if(m>=20) {
int ans=1;
while(true) {
int cnt=0;
for(int i=0;i<N;i++) {
if(marked[i])continue;
move_inside(i);
int res = press_button();
if(res>1) {
move_outside(i);
}
else {
cnt++;
marked[i]=true;
to_remove.push_back(i);
}
}
if(cnt<m) {
return ans;
}
ans++;
for(int x: to_remove) move_outside(x);
to_remove.clear();
}
}
else {
int ans=INT_MAX;
bool marked2[N]; memset(marked2,false,sizeof(marked2));
while(true) {
for(int i=0;i<N;i++) {
if(!marked2[i])move_inside(i);
}
int sz = press_button();
if(sz==0) break;
int idx = 0;
for(int i=0;i<N;i++) {
move_outside(i);
int res=press_button();
//cout<<res<<"\n";
if(res<sz) {
idx=i;
break;
}
}
for(int i=idx+1;i<N;i++) move_outside(i);
move_inside(idx);
marked2[idx]=true;
for(int i=idx+1;i<N;i++) {
move_inside(i);
int res=press_button();
if(res==2) {
marked2[i]=true;
}
move_outside(i);
}
move_outside(idx);
ans=min(ans,sz);
//for(int i=0;i<N;i++) cout<<marked2[i]<<" ";
//cout<<"\n";
}
return ans;
}
}
