# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
988518 | 2024-05-25T05:16:10 Z | cnn008 | 드문 곤충 (IOI22_insects) | C++17 | 0 ms | 0 KB |
#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 const int N=1e5+5; const int mod=1e9+7; int min_cardinality(int n){ set <int> s; int cad=0; auto add = [&](int i){ s.insert(i); move_inside(i); }; auto del = [&](int i){ s.erase(i); move_outside(i); }; // auto check = [&](int k) -> bool{ // for(int i=0; i<n; i++){ // add(i); // if(press_button()>k) del(i); // } // bool f=((int)s.size()>=cad*k); // for(auto i:s) del(i); // return f; // }; for(int i=0; i<n; i++){ add(i); if(press_button()==1) cad++; else del(i); } for(auto i:s) del(i); int l=2,r=n/cad,ans=1; while(l<=r){ int mid=(l+r)/2,f; for(int i=0; i<n; i++){ add(i); if(press_button()>k) del(i); } bool f=((int)s.size()>=cad*k); for(auto i:s) del(i); if(f){ ans=mid; l=mid+1; }else r=mid-1; } return ans; } /** /\_/\ * (= ._.) * / >💖 \>💕 **/