#include <bits/stdc++.h>
void move_inside(int i);
void move_outside(int i);
int press_button();
using namespace std;
int min_cardinality(int N) {
// if we limit the acceptor to 1, we're gonna get the first occurence of each
// element this lets us count the number of elements
// then, if we pass again and limit the acceptor to 2, we get the first and
// second occurences of each element
// eventually, we'll get to a point where x occurences will not have x * <num
// in first> this is when an element only has < x occurences
vector<int> used(N);
// vector<int> firsts;
for (int i = 0; i < N; ++i) {
move_inside(i);
used[i] = 1;
if (press_button() == 2) {
move_outside(i);
used[i] = 0;
}
}
int num_elems = accumulate(used.begin(), used.end(), 0);
if (num_elems == 1) {
return N;
}
if (num_elems == N) {
return 1;
}
int n = N;
vector<int> idxs(n);
iota(idxs.begin(), idxs.end(), 0);
int lo = 1, hi = n / num_elems;
while (lo < hi) {
int mi = (lo + hi + 1) / 2;
vector<int> stk;
for (int i = 0; i < n; ++i) {
if (used[idxs[i]]) {
continue;
}
stk.push_back(idxs[i]);
move_inside(idxs[i]);
if (press_button() > mi) {
move_outside(idxs[i]);
stk.pop_back();
}
}
if (accumulate(used.begin(), used.end(), 0) + int(stk.size()) == mi * num_elems) {
lo = mi;
for (int &i : stk) {
used[i] = true;
}
} else {
hi = mi - 1;
for (int &i : stk) {
move_outside(i);
}
idxs = stk;
for (int i = 0; i < N; ++i) {
if (used[i]) {
idxs.push_back(i);
}
}
n = idxs.size();
hi = min(hi, n / num_elems);
}
}
assert(lo == hi);
return lo;
}
#ifdef MACOS_LOCAL
#include "stub.cpp"
#endif
