#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 time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |