Submission #643650

#TimeUsernameProblemLanguageResultExecution timeMemory
643650VanillaRarest Insects (IOI22_insects)C++17
47.50 / 100
252 ms520 KiB
#include <bits/stdc++.h> #include "insects.h" using namespace std; int min_cardinality(int n) { vector <bool> vis (n); int tp = 0; for (int i = 0; i < n; i++){ move_inside(i); if (press_button() == 2) { move_outside(i); } else { vis[i] = 1; tp++; } } for (int i = 0; i < n; i++) if (vis[i]) move_outside(i); int l = 0, r = n, rs = -1; while (l <= r){ int mid = (l + r) / 2; auto check = [n, tp] (int x) -> bool { vector <int> vis (n); int ins = 0; for (int i = 0; i < n; i++){ move_inside(i); // cout << x << " " << i << " " << ins << " " << press_button() << "\n"; if (press_button() > x) { move_outside(i); } else { ins++; vis[i] = 1; } } for (int i = 0; i < n; i++) if (vis[i]) move_outside(i); return ins == x * tp; }; if (check(mid)) { rs = mid; l = mid + 1; } else { r = mid - 1; } } return rs; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...