Submission #988558

#TimeUsernameProblemLanguageResultExecution timeMemory
988558cnn008Rarest Insects (IOI22_insects)C++17
99.89 / 100
39 ms1912 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; // vector <int> p(n); // iota(p.begin(),p.end(),0); // shuffle(p.begin(),p.end(),rng); map <int,set<int>> mp; int cad; auto add = [&](int i) -> void{ s.insert(i); move_inside(i); }; auto del = [&](int i) -> void{ s.erase(i); move_outside(i); }; // auto check = [&](int k) -> bool{ // nw.clear(); // auto op=*mp.lower_bound(k); // for(auto i:op.second){ // if(s.find(i)!=s.end()) continue; // add(i); // if(press_button()>k) del(i); // else nw.push_back(i); // } // mp[k]=s; // return (int)s.size()>=cad*k; // }; for(int i=0; i<n; i++){ add(i); if(press_button()>1) del(i); } cad=(int)s.size(); mp[1]=s; for(int i=0; i<n; i++) mp[n].insert(i); int l=2,r=n/cad,ans=1; while(l<=r){ int mid=(l+r)/2; vector <int> nw; auto op=mp.lower_bound(mid); for(auto i:(*op).second){ if(s.find(i)!=s.end()) continue; add(i); if(press_button()>mid) del(i); else nw.push_back(i); } mp[mid]=s; if((int)s.size()>=cad*mid){ ans=mid; l=mid+1; }else{ r=mid-1; for(auto i:nw) del(i); } } return ans; } /** /\_/\ * (= ._.) * / >💖 \>💕 **/

Compilation message (stderr)

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