#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 using namespace std; const int MAX=2e5+10; int n; set<int> a; set<int> b; set<int> st; bool check(int m){ // for(int x:a)st.in(x); vector<int> vec; vector<int> vec1; for(int i:b){ move_inside(i); if(press_button()>m){ move_outside(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(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++){ move_inside(i); if(press_button()==2){ b.in(i); move_outside(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; }