#include "insects.h"
#include <vector>
#include <algorithm>
#include <cassert>
#include <iostream>
#include <random>
using namespace std;
enum State {
OUTSIDE, INSIDE, DISCARDED
};
mt19937 gen(1337);
int N, T;
int cnt_inside;
vector<int> state;
void MOVE_IN(int n) {
// cerr << "+ " << n << endl;
assert(state[n] == OUTSIDE);
move_inside(n);
state[n] = INSIDE;
++cnt_inside;
}
void MOVE_OUT(int n) {
// cerr << "- " << n << endl;
assert(state[n] == INSIDE);
move_outside(n);
state[n] = OUTSIDE;
--cnt_inside;
}
bool check(int x) {
vector<int> order(N);
iota(order.begin(), order.end(), 0);
for (int i = 0; i < N and cnt_inside < T * x; ++i) {
int n = order[i];
if (state[n] != OUTSIDE)
continue;
MOVE_IN(n);
int f = press_button();
if (f > x)
MOVE_OUT(n);
}
return cnt_inside == T * x;
}
void RESTORE(const vector<int>& orig_state) {
for (int n = 0; n < N; ++n) {
if (state[n] != orig_state[n]) {
assert(orig_state[n] == OUTSIDE);
MOVE_OUT(n);
}
else if (state[n] == OUTSIDE) {
state[n] = DISCARDED;
}
}
}
int min_cardinality(int _N) {
N = _N;
T = _N;
cnt_inside = 0;
state.assign(N, OUTSIDE);
check(1);
T = cnt_inside;
int res = 1;
int lo = 2, hi = N / T;
while (lo <= hi) {
int mid = lo + (hi - lo) / 2;
vector<int> orig_state = state;
if (check(mid)) {
lo = mid+1;
res = mid;
}
else {
hi = mid-1;
RESTORE(orig_state);
}
}
return res;
}
