제출 #629766

#제출 시각아이디문제언어결과실행 시간메모리
629766hltk드문 곤충 (IOI22_insects)C++17
59.03 / 100
169 ms464 KiB
#include "insects.h" #include <vector> #include <algorithm> #include <numeric> #include <random> using namespace std; int min_cardinality(int n) { vector<int> inds(n); iota(inds.begin(), inds.end(), 0); shuffle(inds.begin(), inds.end(), mt19937_64{42}); vector<int> avail; int inside = 0, types = 0; for (int i : inds) { move_inside(i), inside++; if (press_button() == 1) { types++; } else { avail.push_back(i); move_outside(i), inside--; } } if (types == 1 || types == n) { return 1 ^ n ^ types; } int l = 1, r = n / 2; while (l < r) { int m = (l + r) / 2, k = m + 1; vector<int> vin, vout; for (int i : avail) { if (inside == k * types) { vout.push_back(i); continue; } move_inside(i), inside++; if (press_button() > k) { move_outside(i), inside--; vout.push_back(i); } else { vin.push_back(i); } } if (inside < k * types) { for (int u : vin) { move_outside(u), inside--; } avail = vin; r = m; } else { avail = vout; l = m + 1; } } return l; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...