#include "insects.h"
#include <vector>
int min_cardinality(int N) {
int kinds = 0;
std::vector<int> type(N);
for (int i = 0; i < N; ++i) {
move_inside(i);
if (press_button() > 1) {
move_outside(i);
} else {
kinds += 1;
type[i] = 1;
}
}
auto check = [&](int thres) {
int cnt = 0;
std::vector<int> in, out;
for (int i = 0; i < N; ++i) {
if (type[i] == 1) {
cnt += 1;
} else if (type[i] == 0) {
move_inside(i);
if (press_button() > thres) {
move_outside(i);
out.push_back(i);
} else {
in.push_back(i);
}
}
}
if (cnt + (int)in.size() == kinds * thres) {
for (const int i : in) {
type[i] = 1;
}
return true;
} else {
for (const int i : in) {
move_outside(i);
}
for (const int i : out) {
type[i] = -1;
}
return false;
}
};
int ok = 1, ng = N / kinds + 1;
while (ng - ok > 1) {
int md = (ok + ng) / 2;
(check(md) ? ok : ng) = md;
}
return ok;
}
