Submission #944722

#TimeUsernameProblemLanguageResultExecution timeMemory
944722nguyentunglamRarest Insects (IOI22_insects)C++17
99.79 / 100
35 ms1112 KiB
#include "insects.h" #include<bits/stdc++.h> using namespace std; const int NN = 1e5 + 10; bool in[NN]; int min_cardinality(int n) { int type = 0; vector<int> candidate; for(int i = 0; i < n; i++) { move_inside(i); if (press_button() == 1) { ++type; in[i] = 1; } else { move_outside(i); candidate.push_back(i); } } int l = 2, r = n / type, ans = 1; int cur = 1; // cout << type << endl; while (l <= r) { int mid = (l + r + 1) / 2; assert(cur <= mid); int last = cur; for(auto &i : candidate) { move_inside(i); int nxt = press_button(); if (nxt > mid) { move_outside(i); in[i] = 0; } else { cur = nxt; in[i] = 1; } } int total = 0; for(int i = 0; i < n; i++) total += in[i]; vector<int> _candidate; if (cur == mid && mid * type == total) { for(auto &i : candidate) if (!in[i]) _candidate.push_back(i); l = mid + 1; ans = mid; } else { for(auto &i : candidate) if (in[i]) { _candidate.push_back(i); move_outside(i); in[i] = 0; } r = mid - 1; cur = last; } candidate = _candidate; } return ans; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...