Submission #628984

#TimeUsernameProblemLanguageResultExecution timeMemory
628984PlurmRarest Insects (IOI22_insects)C++17
72.95 / 100
137 ms540 KiB
#include "insects.h" #include <bits/stdc++.h> using namespace std; vector<int> perm; void mi(int i){ move_inside(perm[i]); } void mo(int i){ move_outside(perm[i]); } int min_cardinality(int N) { default_random_engine dre(time(NULL)); perm.resize(N); iota(perm.begin(), perm.end(), 0); shuffle(perm.begin(), perm.end(), dre); set<int> specials; specials.insert(0); mi(0); for(int i = 1; i < N; i++){ mi(i); if(press_button() == 2){ mo(i); }else{ specials.insert(i); } } for(int i : specials) mo(i); // 2 cases: #t <= sqrt(N) or #t > sqrt(N) if(specials.size() * specials.size() <= 1.6 * N){ // case 1: use N log2 #t approach using pbsearch vector<tuple<int,int,int>> pbs; int c = -1; for(int i = 0; i < N; i++){ if(specials.count(i) == 0) pbs.push_back({i, 0, c}); else c++; } vector<int> svec(specials.begin(), specials.end()); int ptr = -1; while(true){ bool cont = false; for(auto p : pbs){ if(get<1>(p) != get<2>(p)) cont = true; } if(!cont) break; sort(pbs.begin(), pbs.end(), [](tuple<int,int,int> x, tuple<int,int,int> y){ return (get<1>(x) + get<2>(x)) / 2 < (get<1>(y) + get<2>(y)) / 2; }); while(ptr > (get<1>(pbs.front()) + get<2>(pbs.front())) / 2){ mo(svec[ptr]); ptr--; } vector<tuple<int,int,int>> npbs; for(auto p : pbs){ if(get<1>(p) == get<2>(p)){ npbs.push_back(p); continue; } int mid = (get<1>(p) + get<2>(p)) / 2; for(int i = ptr+1; i <= mid; i++) mi(svec[i]); ptr = mid; mi(get<0>(p)); if(press_button() == 2){ // hi = mid npbs.push_back({get<0>(p), get<1>(p), mid}); }else{ // lo = mid+1 npbs.push_back({get<0>(p), mid+1, get<2>(p)}); } mo(get<0>(p)); } pbs = npbs; } map<int,int> cards; for(int x : specials) cards[x] = 1; for(auto p : pbs) cards[svec[get<1>(p)]]++; int mn = 5000; for(auto x : cards) mn = min(mn, x.second); return mn; }else{ // case 2: use N log2 ans approach using bsearch on ans int lo = 1; int hi = N / specials.size(); int mid; while(lo < hi){ mid = (lo + hi)/2; set<int> machine; for(int i = 0; i < N; i++){ if(specials.count(i) == 0){ mi(i); machine.insert(i); if(press_button() > mid){ machine.erase(i); mo(i); } } } bool ok = false; vector<int> svec(specials.begin(), specials.end()); shuffle(svec.begin(), svec.end(), dre); for(int x : svec){ mi(x); machine.insert(x); if(press_button() == mid){ ok = true; break; } mo(x); machine.erase(x); } for(int x : machine){ mo(x); } if(ok){ hi = mid; }else{ lo = mid+1; } } return lo; } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...