Submission #988542

#TimeUsernameProblemLanguageResultExecution timeMemory
988542cnn008Rarest Insects (IOI22_insects)C++17
0 / 100
40 ms1240 KiB
#include "bits/stdc++.h" using namespace std; #include "insects.h" #ifdef N_N_C #include "debug.h" #else #define cebug(...) "Arya" #endif #define ll long long mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); int rand(int l, int r){ assert(l<=r); return uniform_int_distribution<int> (l,r)(rng); } const int N=1e5+5; const int mod=1e9+7; int min_cardinality(int n){ set <int> s; vector <int> nw,p(n); iota(p.begin(),p.end(),0); shuffle(p.begin(),p.end(),rng); int cad=0; auto add = [&](int i) -> void{ int _i=p[i]; s.insert(_i); move_inside(_i); }; auto del = [&](int i) -> void{ int _i=p[i]; s.erase(_i); move_outside(_i); }; auto clear = [&]() -> void{ auto _s=s; for(auto i:_s) del(i); }; auto check = [&](int k) -> bool{ nw.clear(); for(int i=0; i<n; i++){ if(s.find(p[i])!=s.end()) continue; add(i); if(press_button()>k) del(i); else nw.push_back(p[i]); } return (int)s.size()>=cad*k; }; for(int i=0; i<n; i++){ add(i); if(press_button()==1) cad++; else del(i); } clear(); // if(cad<=9){ // vector <int> vis(n,0); // int type=0; // for(int i=0; i<n; i++){ // if(!vis[i]){ // vis[i]=++type; // move_inside(i); // for(int j=i+1; j<n; j++){ // move_inside(j); // int val=press_button(); // if(val==2) vis[j]=type; // move_outside(j); // } // move_outside(i); // } // } // map <int,int> mp; // for(int i=0; i<n; i++) mp[vis[i]]++; // int ans=INT_MAX; // for(auto [x,y]:mp) ans=min(ans,y); // return ans; // } int l=2,r=n/cad,ans=1; while(l<=r){ int mid=(l+r)/2; if(check(mid)){ ans=mid; l=mid+1; }else{ r=mid-1; for(auto i:nw) del(i); } } return ans; } /** /\_/\ * (= ._.) * / >💖 \>💕 **/

Compilation message (stderr)

insects.cpp:94:9: warning: "/*" within comment [-Wcomment]
   94 | /**  /\_/\
      |
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...