#include "insects.h" #include <bits/stdc++.h> #define ll long long #define sz(s) (int)s.size() #define pb push_back #define in insert #define lb lower_bound #define ub upper_bound #define all(v) v.begin(),v.end() using namespace std; const int MAX=2e5+10; mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); int n; set<int> a; set<int> b; set<int> st; vector<int> pos; bool check(int m){ vector<int> vec; vector<int> vec1; for(int i:b){ move_inside(pos[i]); if(press_button()>m){ move_outside(pos[i]); vec1.pb(i); } else{ st.in(i); vec.pb(i); } if(sz(st)==m*sz(a)){ for(int x:vec)b.erase(x); return 1; } } if(sz(st)<m*sz(a)){ for(int x:vec){ move_outside(pos[x]); st.erase(x); } for(int x:vec1)b.erase(x); } else{ for(int x:vec)b.erase(x); } return (sz(st)==m*sz(a)); } int min_cardinality(int N){ n=N; for(int i=0;i<n;i++)pos.pb(i); shuffle(all(pos),rng); for(int i=0;i<N;i++){ move_inside(pos[i]); if(press_button()==2){ b.in(i); move_outside(pos[i]); } else{ st.in(i); a.in(i); } } int l=1,r=N/sz(a),res=1; while(l<=r){ int m=(l+r)/2; if(check(m)){ l=m+1; res=m; } else r=m-1; } return res; }