Submission #1074769

#TimeUsernameProblemLanguageResultExecution timeMemory
1074769fv3Rarest Insects (IOI22_insects)C++17
0 / 100
31 ms596 KiB
#include "insects.h" #include <bits/stdc++.h> using namespace std; int min_cardinality(int N) { // Find the number of different insect types: // Maximum number of insects with 1 being maximum // Let that number be K // Find another set of K numbers with 2 being the maximum // Then 3 and 4 and so on untill it is no longer possible // The grader is not adaptive: vector<int> indicies(N); iota(indicies.begin(), indicies.end(), 0); mt19937 mt(time(0)); shuffle(indicies.begin(), indicies.end(), mt); vector<int> in(N); vector<int> order; int k = 0; int insect_cnt = 0; for (int i = 0; i < N; i++) { move_inside(indicies[i]); if (press_button() > 1) { move_outside(indicies[i]); } else { k++; insect_cnt++; order.push_back(i); in[i] = 1; } } int l = 0, r = N / k + 1; while (l < r) { int c = (l + r + 1) / 2; while (insect_cnt > k * c) { move_outside(indicies[order.back()]); order.pop_back(); insect_cnt--; } for (int i = 0; i < N && insect_cnt < k * c; i++) { if (in[i]) continue; move_inside(indicies[i]); if (press_button() > c) { move_outside(indicies[i]); } else { insect_cnt++; order.push_back(i); in[i] = 1; } } if (insect_cnt < k * c) r = c - 1; else l = c; } return l; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...