#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), isuq(n, 0), ban(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; } for (int i=0; i<n; ++i)if (got[i])isuq[i]=got[i]; if (uq==1)return n; int low=1, high=n/uq+1; while (low+1<high){ int mid=(low+high)/2, c=0; vector<bool> toomuch(n, 0), added(n, 0); for (int i=0; i<n; ++i)if (got[i])++c; for (int i=0; i<n; ++i)if (!got[i]&&!ban[i]){ move_inside(i); got[i]=1; added[i]=1; if (press_button()>mid)move_outside(i), got[i]=0, added[i]=0, toomuch[i]=1; else ++c; } if (c==uq*mid)low=mid; else{ high=mid; for (int i=0; i<n; ++i)if (added[i]&&!isuq[i])move_outside(i), got[i]=0; for (int i=0; i<n; ++i)if (toomuch[i])ban[i]=1; } } return low; }