#include "insects.h" #include <bits/stdc++.h> using namespace std; int min_cardinality(int N) { int cnt = 0; vector<bool> f(N); for (int i = 0; i < N; i++) { move_inside(i); if (press_button() <= 1) { f[i] = 1; cnt++; } else { move_outside(i); } } vector<int> blocked(N); for (int i = 0; i < N; i++) { if (f[i]) { blocked[i] = 1; } } int lo = 1, hi = N / cnt, in = cnt; while (lo < hi) { int mi = (lo + hi + 1) / 2; vector<int> t; for (int i = 0; i < N; i++) { if (f[i] || blocked[i]) { continue; } t.push_back(i); } random_shuffle(t.begin(), t.end()); for (int i : t) { move_inside(i); if (press_button() <= mi) { in++; f[i] = 1; } else { move_outside(i); } } if (in == mi * cnt) { for (int i = 0; i < N; i++) { if (f[i]) { blocked[i] = 1; } } lo = mi; } else { hi = in / cnt; for (int i = 0; i < N; i++) { if (!f[i]) { blocked[i] = 1; } if (blocked[i]) { continue; } if (f[i]) { f[i] = 0; in--; move_outside(i); } } } } return lo; }