Submission #1025129

#TimeUsernameProblemLanguageResultExecution timeMemory
1025129mansurRarest Insects (IOI22_insects)C++17
100 / 100
44 ms1104 KiB
#include "insects.h" #include <bits/stdc++.h> using namespace std; #define rall(s) s.rbegin(), s.rend() #define all(s) s.begin(), s.end() #define sz(s) (int) s.size() #define s second #define f first using ll = long long; using pii = pair<int, int>; using pll = pair<ll, ll>; mt19937_64 rng(131415889); int min_cardinality(int n) { vector<int> p(n), pos; for (int i = 0; i < n; i++) p[i] = i; shuffle(all(p), rng); int k = 0; for (int i = 0; i < sz(p); i++) { move_inside(p[i]); if (press_button() == 1) { k++; pos.push_back(p[i]); }else move_outside(p[i]); } for (int x: pos) move_outside(x); int l = 1, r = n / k, ans = 0; while (l <= r) { int m = (l + r) / 2; vector<int> s0, s1; for (int i = 0; i < sz(p); i++) { if (sz(s0) == m * k) { s1.push_back(p[i]); continue; } move_inside(p[i]); if (press_button() > m) { move_outside(p[i]); s1.push_back(p[i]); }else s0.push_back(p[i]); } for (int x: s0) move_outside(x); if (sz(s0) == m * k) { p = s1; l = 1; r -= m; ans += m; }else p = s0, r = m - 1; } return ans; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...