Submission #787661

#TimeUsernameProblemLanguageResultExecution timeMemory
787661khshgRarest Insects (IOI22_insects)C++17
53.11 / 100
138 ms532 KiB
#include"insects.h" #include<bits/stdc++.h> using namespace std; int min_cardinality(int N) { int k; int D = 0; set<int> INs; for(int i = 0; i < N; ++i) { INs.insert(i); move_inside(i); k = press_button(); if(k == 2) { INs.erase(i); move_outside(i); continue; } ++D; } int tl = 1, tr = N / D; while(tl < tr) { int tm = (tl + tr + 1) / 2; for(int i = 0; i < N; ++i) { if(!INs.insert(i).second) continue; move_inside(i); k = press_button(); if(k > tm) { INs.erase(i); move_outside(i); continue; } if(D * tm == (int)INs.size()) break; } if((int)INs.size() < D * tm) { tr = tm - 1; if(tl == tr) continue; tm = (tl + tr + 1) / 2; for(int i = N - 1; i >= 0; --i) { if(INs.find(i) == end(INs)) continue; k = press_button(); if(k > tm) { INs.erase(i); move_outside(i); } else break; } } else { tl = tm; } } return (tl + tr) / 2; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...