#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;
}
int mini = n;
for (int i : reprezentant) {
taken[i] = true;
int me = 1; // doar pe i
move_inside(i);
for (int x : order) {
if (me >= mini) {
break;
}
if (!taken[x]) {
move_inside(x);
if (press_button() == 2) {
taken[x] = true;
me++;
}
move_outside(x);
}
}
move_outside(i);
mini = std::min(mini, me);
}
return mini;
}
