#include "insects.h"
#include <vector>
#include <algorithm>
#include <cassert>
#include <random>
#include <iostream>
std::mt19937 rng(123);
#define debug(x) #x << " = " << x << '\n'
int min_cardinality(int n) {
std::vector<int> type(n, 0);
std::vector<int> reprezentant;
for (int i = 0; i < n; i++) {
move_inside(i);
if (press_button() == 2) {
move_outside(i);
} else {
type[i] = 1;
reprezentant.push_back(i);
}
}
int D = (int) reprezentant.size();
if (D == 1) {
return n;
}
if (D > n / 2) {
return 1;
}
auto check = [&](int mid) {
for (int i = 0; i < n; i++) {
if (type[i] == 0) {
move_inside(i);
if (press_button() > mid) {
move_outside(i);
} else {
type[i] = 1;
}
}
}
int inside = 0;
for (int i = 0; i < n; i++) {
if (type[i] == 1 || type[i] == 2) {
inside++;
}
}
return inside == D * mid;
};
int l = 1, r = n / D;
while (l < r) {
int mid = (l + r + 1) / 2;
if (check(mid)) {
l = mid;
for (int i = 0; i < n; i++) {
if (type[i] == 1) {
type[i] = 2;
}
}
} else {
r = mid - 1;
for (int i = 0; i < n; i++) {
if (type[i] == 1) {
move_outside(i);
type[i] = 0;
} else if (type[i] == 0) {
type[i] = -1;
}
}
}
}
return r;
}
