Submission #1074801

#TimeUsernameProblemLanguageResultExecution timeMemory
1074801fv3Rarest Insects (IOI22_insects)C++17
43.30 / 100
163 ms712 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; } } if (k < sqrt(N)) { int res = 1; while (true) { int cnt = 0; for (int i = 0; i < N && cnt < k; i++) { if (in[i]) continue; move_inside(indicies[i]); if (press_button() > res + 1) { move_outside(indicies[i]); } else { cnt++; in[i] = 1; } } if (cnt < k) return res; res++; } return res; } int l = 1, r = N / k; while (l < r) { int c = (l + r + 1) / 2; while (insect_cnt > k * l) { move_outside(indicies[order.back()]); in[order.back()] = 0; 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) l = c; else r = c - 1; } return l; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...