#include "insects.h" #include <bits/stdc++.h> using namespace std; #define pb push_back #define mp make_pair #define pii pair<int, int> #define fi first #define se second int min_cardinality(int n){ int uq=1; move_inside(0); vector<bool> got(n, 0); for (int i=1; i<n; ++i){ move_inside(i); got[i]=1; if (press_button()==2)move_outside(i), got[i]=0; else ++uq; } if (uq==1)return n; int low=1, high=n/uq+1; while (low+1<high){ int mid=(low+high)/2, c=0; vector<int> temp; for (int i=0; i<n; ++i)if (!got[i]){ move_inside(i); got[i]=1; if (press_button()>mid)move_outside(i), got[i]=0; else ++c; } if (c==uq*mid)low=mid; else{ high=mid; for (int i=0; i<n; ++i)if (got[i])move_outside(i), got[i]=0; } } return low; }