# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
838326 | 2023-08-26T15:22:44 Z | Baytoro | Rarest Insects (IOI22_insects) | C++17 | 0 ms | 0 KB |
#include <bits/stdc++.h> using namespace std; #include "insects.h" /#include "stub.cpp" #define ll long long #define sc second #define fr first #define pb push_back int min_cardinality(int n) { vector<int> used(n); int cnt=0; auto in = [&](int x){ if(!used[x]){ cnt++; used[x]=1; move_inside(x); } }; auto out = [&](int x){ if(used[x]){ cnt--; used[x]=0; move_outside(x); } }; for(int i=0;i<n;i++){ in(i); if(press_button()>1){ out(i); } } int ans=0; if(cnt==1) return n; int s=cnt; int l=1,r=n/s+1; const int A=50,B=50; vector<int> a(n); while(r-l>1){ int md=(A*l+B*r)/(A+B); if(md==r) md--; else if(md==l) md++; for(int i=0;i<n;i++){ if(!a[i] && used[i]) out(i); } for(int i=0;i<n && cnt<md*s;i++){ if(!a[i]){ in(i); if(press_button()>md) out(i); } } for(int i=0;i<n;i++){ if(!a[i]){ if(cnt==md*s && used[i]) a[i]++; else if(cnt!=md*s && !used[i]) a[i]++; } } if(cnt==md*s) l=md; else r=md; } return ans; }