Submission #1074799

#TimeUsernameProblemLanguageResultExecution timeMemory
1074799ZicrusRarest Insects (IOI22_insects)C++17
0 / 100
1 ms596 KiB
#include <bits/stdc++.h> #include "insects.h" using namespace std; typedef long long ll; int n; vector<bool> in; unordered_set<int> s; int cnt; int add(int i) { if (in[i]) return 0; move_inside(i); cnt++; in[i] = true; return 1; } int remove(int i) { if (!in[i]) return 0; move_outside(i); cnt--; in[i] = false; return 1; } int min_cardinality(int N) { n = N; cnt = 0; mt19937 mt(time(0)); in = vector<bool>(n); for (int i = 0; i < n; i++) { add(i); } int mx = press_button(); int prevSz = cnt; while (mx > 1) { int cur = mx; while (cur == mx) { int i = mt()%n; if (remove(i)) { cur = press_button(); if (cur == mx) s.insert(i); } } for (auto &e : s) { if (add(e)) { cur = press_button(); if (cur == mx) remove(e); } } s.clear(); if (cnt * mx / (mx-1) == prevSz) { break; } prevSz = cnt; mx--; } return mx; } #ifdef TEST #include "grader.cpp" #endif
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...