제출 #1203139

#제출 시각아이디문제언어결과실행 시간메모리
1203139LucaLucaMRarest Insects (IOI22_insects)C++20
0 / 100
0 ms412 KiB
#include "insects.h" #include <vector> #include <algorithm> #include <cassert> #include <random> #include <iostream> std::mt19937 rng(123); int min_cardinality(int n) { std::vector<int> reprezentant; std::vector<int> order(n); for (int i = 0; i < n; i++) { order[i] = i; } std::shuffle(order.begin(), order.end(), rng); for (int i : order) { move_inside(i); if (press_button() >= 2) { move_outside(i); } else { reprezentant.push_back(i); } } std::vector<bool> taken(n, false); if ((int) reprezentant.size() > n / 2) { return 1; } int D = (int) reprezentant.size(); if (D >= 15) { // caut binar ts auto check = [&](int mid) { std::vector<int> inside; for (int i : order) { move_inside(i); inside.push_back(i); if (press_button() > mid) { move_outside(i); inside.pop_back(); } } int sz = (int) inside.size(); for (int i : inside) { move_outside(i); } if (sz == D * mid) { return true; } else { return false; } }; int l = 1, r = n / D; while (l < r) { int mid = (l + r + 1) / 2; if (check(mid)) { l = mid; } else { r = mid - 1; } } return r; } else { std::vector<int> where(n, 0); for (int i : reprezentant) { where[i] = -1; } for (int bit = 0; bit <= std::__lg(n); bit++) { for (int i = 0; i < D; i++) { if (i >> bit & 1) { move_inside(reprezentant[i]); } } for (int i = 0; i < n; i++) { if (where[i] != -1) { move_inside(i); if (press_button() == 2) { where[i] |= 1 << bit; } move_outside(i); } } for (int i = 0; i < D; i++) { if (i >> bit & 1) { move_outside(reprezentant[i]); } } } std::vector<int> f(D, 1); for (int i = 0; i < n; i++) { if (where[i] != -1) { f[where[i]]++; } } return *std::min_element(f.begin(), f.end()); } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...