#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; for(int i:b){ move_inside(i); if(press_button()>m){ move_outside(i); } else{ st.in(i); vec.pb(i); } } if(sz(st)<m*sz(a)){ for(int x:vec){ move_outside(x); st.erase(x); } } // cout<<m<<" "<<sz(st)<<" "<<m*sz(a)<<"\n"; // 0 33 // 1 41 // 2 40 // 3 41 // 4 45 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{ 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; }