#include "insects.h"
#include <bits/stdc++.h>
using namespace std;
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
vector<int> p;
int cnt;
int pressButton() {
return press_button();
}
void moveInside(int i) {
move_inside(p[i]);
}
void moveOutside(int i) {
move_outside(p[i]);
}
int minCardinality(int N) {
vector<int> candidates(N);
iota(candidates.begin(), candidates.end(), 0);
int coef = 0;
int lo = 1, hi = N/cnt+1;
while (hi - lo > 1) {
hi = min(hi, coef + int(candidates.size() / cnt) + 1);
int mid = (lo + hi) >> 1;
// cout << lo << ' ' << mid << ' ' << hi << ' ' << candidates.size() << "\n";
vector<int> inside, outside;
int fl = 0;
for (int i : candidates) {
if (coef * cnt + int(inside.size()) == mid*cnt || fl) {
fl = 1;
outside.emplace_back(i);
continue;
}
moveInside(i);
if (pressButton() > mid) {
moveOutside(i);
outside.emplace_back(i);
} else inside.emplace_back(i);
}
if (coef * cnt + int(inside.size()) == mid * cnt) {
lo = mid;
coef = mid;
candidates = outside;
} else {
for (int i : inside) moveOutside(i);
hi = mid;
candidates = inside;
}
}
return lo;
}
/*
9
4 4 4 4 3 3 3 3 3 3
*/
/*
4
2 2 2 3
*/
int min_cardinality(int N) {
p.assign(N, 0);
iota(p.begin(), p.end(), 0);
shuffle(p.begin(), p.end(), rng);
shuffle(p.begin(), p.end(), rng);
shuffle(p.begin(), p.end(), rng);
shuffle(p.begin(), p.end(), rng);
shuffle(p.begin(), p.end(), rng);
vector<int> e;
for (int i = 0; i < N; i++) {
moveInside(i);
if (pressButton() > 1) moveOutside(i);
else {
e.emplace_back(i);
++cnt;
}
}
for (int i : e) moveOutside(i);
if (cnt == 1) return N;
if (cnt == 2) {
for (int i = 0; i < N; i++) moveInside(i);
int T = pressButton();
int O = N-T;
if (O == 0) O = INT_MAX;
return min(O, T);
}
if (cnt == N-1) return 1;
if (cnt == N) return 1;
return minCardinality(N);
}
