#include <numeric>
#include <vector>
struct UnionFind {
std::vector<int> par;
UnionFind(size_t N) : par(N, -1) {}
auto find(int idx) -> int {
if (par[idx] < 0)
return idx;
else
return par[idx] = find(par[idx]);
}
void unite(int l, int r) {
l = find(l);
r = find(r);
if (l == r)
return;
if (-par[l] < -par[r])
std::swap(l, r);
par[l] += par[r];
par[r] = l;
}
};
void move_inside(int i);
void move_outside(int i);
int press_button();
int min_cardinality(int N) {
move_inside(0);
auto dsu = UnionFind(N);
auto included = std::vector<int>{0};
for (int i = 1; i < N; i++) {
move_inside(i);
int card = press_button();
if (card > 1) {
int l = 0;
int r = included.size();
bool filled = true;
while (r - l > 1) {
// We know that the index of the equal one satisfies l <= idx < r
auto m = std::midpoint(l, r);
// We want to test if l <= idx < m
if (filled) {
for (int j = m; j < r; j++)
move_outside(included[j]);
} else {
for (int j = l; j < m; j++)
move_inside(included[j]);
}
if (press_button() > 1) {
r = m;
filled = true;
} else {
l = m;
filled = false;
}
}
dsu.unite(i, included[l]);
if (filled)
move_inside(included[l]);
for (int j = r; j < included.size(); j++)
move_inside(included[j]);
} else {
included.push_back(i);
}
}
int best = -dsu.par[dsu.find(0)];
for (int i = 0; i < N; i++) {
if (dsu.par[i] > 0)
continue;
best = std::min(best, -dsu.par[i]);
}
return best;
}
