#include "insects.h" #include<bits/stdc++.h> #define eb emplace_back int min_cardinality(int N) { std::vector<int>machine; std::vector<bool>inside(N,false),fixed(N,false); for(int i=0;i<N;++i){ move_inside(i); if(press_button()==2){ move_outside(i); } else{ inside[i]=fixed[i]=true; machine.eb(i); } } int uni=machine.size(); int l=1,r=N/uni; while(l<r){ int mid=(l+r+1)>>1,k=0; for(int i=0;i<N;++i){ if(fixed[i]) continue; if(uni*mid==k) break; move_inside(i); k++; if(press_button()>mid){ move_outside(i); k--; } else{ inside[i]=true; machine.eb(i); } } if(uni*mid==k){ l=mid; for(int i=0;i<N;++i){ if(inside[i]) fixed[i]=true; } } else{ r=mid-1; for(int i=0;i<N;++i){ if(!inside[i]){ fixed[i]=true; } else if(!fixed[i]){ move_outside(i); inside[i]=false; machine.pop_back(); } } } } return l; }