#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> firsts;
for (int i = 0; i < N; ++i) {
move_inside(i);
firsts.push_back(i);
if (press_button() == 2) {
move_outside(i);
firsts.pop_back();
}
}
int num_elems = firsts.size();
for (int &i : firsts) {
move_outside(i);
}
if (num_elems == 1) {
return N;
}
if (num_elems == N) {
return 1;
}
int find_iters = num_elems * N;
int bs_iters = N * bit_width(unsigned(N / num_elems));
if (bs_iters < find_iters) {
int x = *ranges::partition_point(views::iota(1, N / num_elems + 1), [&](int x) {
vector<int> v;
for (int i = 0; i < N; ++i) {
move_inside(i);
v.push_back(i);
if (press_button() > x) {
move_outside(i);
v.pop_back();
}
}
for (int &i : v) {
move_outside(i);
}
return int(v.size()) == x * num_elems;
});
return x - 1;
}
vector<bool> used(N);
int ans = 0;
for (int i = 0; i < N; ++i) {
if (used[i]) {
continue;
}
int cur = 1;
used[i] = true;
move_inside(i);
for (int j = i + 1; j < N; ++j) {
if (used[j]) {
continue;
}
move_inside(j);
if (press_button() > 1) {
used[j] = true;
cur++;
}
move_outside(j);
}
move_outside(i);
ans = max(ans, cur);
}
return ans;
}
#ifdef MACOS_LOCAL
#include "stub.cpp"
#endif
