제출 #629060

#제출 시각아이디문제언어결과실행 시간메모리
629060two_sides드문 곤충 (IOI22_insects)C++17
99.95 / 100
57 ms428 KiB
#include "insects.h" #include <bits/stdc++.h> namespace { using namespace std; const int N = 2000; mt19937 rng(chrono::high_resolution_clock ::now().time_since_epoch().count()); bool inside[N], dead[N]; int cnt; vector<int> ord; void insert(int i) { cnt++; inside[i] = 1; move_inside(ord[i]); } void erase(int i) { cnt--; inside[i] = 0; move_outside(ord[i]); } } int min_cardinality(int n) { ord.resize(n); iota(ord.begin(), ord.end(), 0); for (int i = 0; i < n; i++) { insert(i); if (press_button() > 1) erase(i); } int t = cnt, l = 1, r = n / cnt; while (l < r) { int m = (l + r + 1) / 2; vector<int> add, remove; for (int i = 0; i < n; i++) if (!inside[i] && !dead[i]) { insert(i); if (press_button() > m) { erase(i); remove.push_back(i); } else { add.push_back(i); if (cnt == m * t) break; } } if (cnt == m * t) l = m; else { for (int i : add) erase(i); for (int i : remove) dead[i] = 1; r = m - 1; } } return l; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...