# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
859280 | 2023-10-10T03:16:48 Z | imarn | Rarest Insects (IOI22_insects) | C++17 | 0 ms | 0 KB |
#include<bits/stdc++.h> #include "insects.h" #define f first #define s second #define pb push_back using namespace std; int siz[2001]{0}; int min_cardinality(int N) { vector<int>vec; bool vis[2001]={0}; move_inside(0); int sz=0; for(int i=0;i<N;i++)siz[i]=1; for(int i=0;i<N;i++){ if(vis[i])continue; move_inside(i); if(press_button()==1){ vis[i]=1;sz++;vec.pb(i); } else move_outside(i); } if(sz>sqrt(N)){ int now=2; while(sz<N){ for(int i=1;i<N;i++){ if(vis[i])continue; move_inside(i); if(press_button()==now){ vis[i]=1;sz++; } else move_outside(i); }now++; }return now-1; } else { for(int i=0;i<N;i++)if(vis[i])move_outside(i); for(int i=0;i<N;i++){ if(!vis[i]){ move_inside(i); for(auto it : vec){ move_inside(it); if(press_button()==2){ siz[it]++; move_outside(i); move_uotside(it); break; } else move_outside(it); } } } int ans=1e9; for(auto it : vec){ ans=min(ans,siz[it]); }return ans; } return 0; }