Submission #1084684

#TimeUsernameProblemLanguageResultExecution timeMemory
1084684siewjhRarest Insects (IOI22_insects)C++17
99.89 / 100
44 ms856 KiB
#include "insects.h" #include <bits/stdc++.h> using namespace std; int min_cardinality(int N){ vector<int> active; int cnt = 0; for (int i = 0; i < N; i++){ move_inside(i); if (press_button() == 1) cnt++; else{ move_outside(i); active.push_back(i); } } int ans = 1, l = 2, r = N / cnt, sz = cnt; while (l <= r){ int m = (l + r) >> 1; vector<int> iv, ov; for (int i : active){ move_inside(i); if (press_button() <= m){ iv.push_back(i); sz++; } else{ move_outside(i); ov.push_back(i); } } if (sz == cnt * m){ ans = m; l = m + 1; active = ov; } else{ r = m - 1; for (int i : iv) move_outside(i); sz -= iv.size(); active = iv; } } return ans; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...