Submission #831330

#TimeUsernameProblemLanguageResultExecution timeMemory
831330definitelynotmeeRarest Insects (IOI22_insects)C++17
100 / 100
55 ms484 KiB
// Fifth submission after reading edi #include "insects.h" #include<bits/stdc++.h> #define all(x) x.begin(), x.end() using ll = long long; using namespace std; template<typename T> using matrix = vector<vector<T>>; struct Machine { set<int> s; void insert(int id){ s.insert(id); move_inside(id); } void erase(int id){ s.erase(id); move_outside(id); } int resp(){ return press_button(); } void clear(){ auto it = s.begin(); while(it!=s.end()){ move_outside(*it); it = s.erase(it); } } }; int min_cardinality(int N) { mt19937 rng(time(nullptr)); vector<int> dif; vector<int> v; Machine m; for(int i = 0; i < N; i++){ m.insert(i); if(m.resp() == 1){ dif.push_back(i); } else m.erase(i); v.push_back(i); } shuffle(all(v),rng); m.clear(); int ini = 1, fim = N/dif.size(); vector<int> curinsert, lastinsert; auto putless =[&](int mx){ for(int i : v){ if(m.s.count(i)) continue; m.insert(i); if(m.resp() > mx) m.erase(i); else curinsert.push_back(i); if(m.s.size() == dif.size()*mx) break; } }; int last = -1; while(ini!=fim){ int mid = (ini+fim+1)>>1; // cerr << "mid = " << mid << '\n'; if(mid < last){ vector<int> newv; for(int i : m.s) newv.push_back(i); swap(v,newv); for(int i : lastinsert) m.erase(i); } putless(mid); bool ok = m.s.size()%mid == 0 && m.s.size()/mid == dif.size(); if(ok) ini = mid; else fim = mid-1; last = mid; swap(curinsert,lastinsert); curinsert.clear(); } return ini; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...