Submission #1075182

#TimeUsernameProblemLanguageResultExecution timeMemory
1075182ZicrusRarest Insects (IOI22_insects)C++17
64.49 / 100
96 ms932 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; while (!remove(i)) i = mt()%n; int j = mt()%n; while (!remove(j)) j = mt()%n; cur = press_button(); if (cur == mx) { s.insert(i); s.insert(j); } else { add(j); cur = press_button(); if (cur == mx) { s.insert(i); remove(j); } cur = mx-1; } } for (auto &e : s) { if (add(e)) { cur = press_button(); if (cur == mx) remove(e); } } if (cnt * mx % (mx-1) == 0 && cnt * mx / (mx-1) == prevSz) { break; } s.clear(); 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...