Submission #627972

#TimeUsernameProblemLanguageResultExecution timeMemory
627972tutisRarest Insects (IOI22_insects)C++17
83.73 / 100
111 ms336 KiB
#include "insects.h" #include <bits/stdc++.h> using namespace std; mt19937_64 rng(0); int min_cardinality(vector<int> x) { shuffle(x.begin(), x.end(), rng); int N = x.size(); int add2 = 0; int add1 = 0; vector<int>y; int lo, hi; int c = 0; auto cnt = [&](int m)->int { vector<int>v; y = {}; int k = 0; bool jau = false; int liko = (int)x.size(); for (int i : x) { if (!jau) v.push_back(i); if (!jau) move_inside(i); if (!jau) k = press_button(); if (k + add1 == m + 1 || jau) { if (!jau) v.pop_back(); if (!jau) move_outside(i); y.push_back(i); } liko--; if (c != 0) if ((int)v.size() + add2 == m * c) jau = true; if (c != 0) if ((int)v.size() + add2 + liko < m * c) jau = true; } int r = v.size(); for (int i : v) move_outside(i); return add2 + r; }; c = cnt(1); if (c * 2 > N) return 1; { x = y; add2 = c; add1 = 1; } lo = 1; hi = N / c; double bias = 3.2; bool fst = true; while (lo < hi) { int m = round((lo * bias + hi * 1.0) / (bias + 1)); if (fst) m = round((lo * 2 + hi * 1.0) / (2 + 1)); m = max(m, lo + 1); m = min(m, hi); int k = cnt(m); if (k == m * c) { lo = m; x = y; add2 = m * c; add1 = m; } else hi = m - 1; fst = false; } return lo; } int min_cardinality(int N) { vector<int>v; for (int i = 0; i < N; i++) v.push_back(i); return min_cardinality(v); }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...