#include "insects.h" #include<bits/stdc++.h> using namespace std; set<int> s; void in(int i){ s.insert(i); move_inside(i); } void out(int i){ s.erase(i); move_outside(i); } int min_cardinality(int n){ for (int i=0; i<n; ++i){ in(i); if (press_button()>1) out(i); } int cnt=s.size(); map<int, set<int>> memo; memo[1]=s; for (int i=0; i<n; ++i) memo[n].insert(i); int l=2, r=n/cnt; while (l<=r){ int mid=(l+r)>>1; auto it=memo.lower_bound(mid); set<int> t; for (int i:it->second) if (!s.count(i)){ in(i); if (press_button()>mid) out(i); else t.insert(i); } int k=s.size(); memo[mid]=s; if (k>=cnt*mid) l=mid+1; else{ r=mid-1; for (int i:t) out(i); } } return r; return 0; }