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