#include "insects.h"
#include <bits/stdc++.h>
using namespace std;
#define FOR(i, a, b) for (int i = (a); i < (b); i++)
#define bg(x) (x).begin()
#define en(x) (x).end()
#define all(x) bg(x), en(x)
#define sz(x) (int) (x).size()
typedef long long ll;
using vi = vector<int>;
using vvi = vector<vi>;
using vl = vector<ll>;
int PUT_IN = 0, TAKE_OUT = 0, PRESS = 0;
vector<int> INDICES;
void put(int i) {
i = INDICES[i];
PUT_IN++;
move_inside(i);
}
void take(int i) {
i = INDICES[i];
TAKE_OUT++;
move_outside(i);
}
int press() {
PRESS++;
return press_button();
}
struct DSU {
int n;
vi par, siz;
DSU(int N) {
n = N;
par.resize(n); iota(all(par), 0);
siz.assign(n, 1);
}
int find_set(int v) {
if (par[v] == v) return v;
return par[v] = find_set(par[v]);
}
void union_set(int a, int b) {
a = find_set(a);
b = find_set(b);
if (a != b) {
if (siz[a] < siz[b]) swap(a, b);
par[b] = a;
siz[a] += siz[b];
}
}
};
int quadratic(int N) {
auto dsu = DSU(N);
FOR(i, 0, N) {
move_inside(i);
FOR(j, 0, N) {
// todo see if I can reduce checks where I already know that there isn't an edge between set a and set b
if(dsu.find_set(i) == dsu.find_set(j)) continue;
move_inside(j);
if (press_button() > 1) {
dsu.union_set(i, j);
}
move_outside(j);
}
move_outside(i);
}
int minsz = INT_MAX;
FOR(i, 0, N) minsz = min(minsz, dsu.siz[dsu.find_set(i)]);
return minsz;
}
void window_range(int N, int L, int R, set<int> &active, DSU &dsu) {
int cursz = 1;
for (int i = L; i <= R; i++) {
move_inside(i);
int newsz = press_button();
if (newsz > cursz) {
int toerase = -1;
for (auto &el : active) {
move_outside(el);
if (press_button() < newsz) {
dsu.union_set(i, el);
toerase = el;
break;
} else {
move_inside(el);
}
}
if (toerase != -1) active.erase(toerase);
}
active.insert(i);
}
for (auto &el : active) {
move_outside(el);
}
active.clear();
}
void combine_sets(int N, DSU &dsu, int L1, int R1, int L2, int R2) {
set<int> p1, p2;
FOR(i, L1, R1 + 1) {
p1.insert(dsu.find_set(i));
}
FOR(i, L2, R2 + 1) {
p2.insert(dsu.find_set(i));
}
for (auto &el1 : p1) {
move_inside(el1);
for (auto &el2 : p2) {
move_inside(el2);
if (press_button() > 1) {
dsu.union_set(el1, el2);
}
move_outside(el2);
}
move_outside(el1);
}
}
int window(int N) { // quadratic but faster
auto dsu = DSU(N);
set<int> active;
int L1 = 0, R1 = N / 2, L2 = (N / 2) + 1, R2 = N - 1;
window_range(N, L1, R1, active, dsu);
window_range(N, L2, R2, active, dsu);
combine_sets(N, dsu, L1, R1, L2, R2);
int minsz = INT_MAX;
FOR(i, 0, N) minsz = min(minsz, dsu.siz[dsu.find_set(i)]);
return minsz;
}
int bsearch(int N) {
vector<int> reps(1, 0); put(0);
FOR(i, 1, N) {
put(i);
if (press() > 1) {
take(i);
} else {
reps.push_back(i);
}
}
vector<int> cur_in; for (int i = 0; i < sz(reps); i++) take(reps[i]);
auto dsu = DSU(N);
for (int i = 0; i < N; i++) {
if (count(all(reps), i)) continue;
int lo = 0, hi = sz(reps);
while (lo < hi) {
int mid = lo + (hi - lo) / 2;
for (int j = 0; j <= mid; j++) {
cur_in.push_back(reps[j]); put(reps[j]);
}
put(i);
int ans = press(); take(i);
while (!cur_in.empty()) take(cur_in.back()), cur_in.pop_back();
if (ans > 1) {
hi = mid;
} else {
lo = mid + 1;
}
}
dsu.union_set(reps[lo], i);
}
int minsz = INT_MAX;
FOR(i, 0, N) minsz = min(minsz, dsu.siz[dsu.find_set(i)]);
return minsz;
}
int bsearch2(int N) {
vector<int> reps(1, 0); put(0);
FOR(i, 1, N) {
put(i);
if (press() > 1) {
take(i);
} else {
reps.push_back(i);
}
}
vector<int> cur_in = reps;
// for (int i = 0; i < sz(reps); i++) take(reps[i]);
auto dsu = DSU(N);
int mlog = 1; while ((1 << mlog) <= sz(reps)) mlog++;
vector<int> subs; FOR(i, 0, N) if (!count(all(reps), i)) subs.push_back(i);
int tsub = sz(subs);
vector<int> LO(tsub, 0), HI(tsub, sz(reps));
bool is_asc = false;
auto pred = [&](int a, int b) {
int av = (LO[a] + (HI[a] - LO[a]) / 2), bv = (LO[b] + (HI[b] - LO[b]) / 2);
return is_asc ? av < bv : av > bv;
};
int cmid = reps.size() - 1;
for (int llg = 0; llg <= mlog; llg++) {
deque<int> orders; FOR(i, 0, tsub) if (LO[i] < HI[i]) orders.push_back(i);
sort(all(orders), pred);
while (!orders.empty()) {
int i = orders.front(); orders.pop_front();
int mid = LO[i] + (HI[i] - LO[i]) / 2;
while (cmid < mid) {
put(reps[cmid+1]);
cur_in.push_back(reps[cmid + 1]);
cmid++;
}
while (cmid > mid) {
take(cur_in.back());
cur_in.pop_back();
cmid--;
}
put(subs[i]);
int ans = press(); take(subs[i]);
if (ans > 1) {
HI[i] = mid;
} else {
LO[i] = mid + 1;
}
int newmid = LO[i] + (HI[i] - LO[i]) / 2;
if ((is_asc ? newmid >= mid : newmid <= mid) && LO[i] < HI[i]) {
orders.insert(upper_bound(all(orders), i, pred), i);
}
}
// while (!cur_in.empty()) take(cur_in.back()), cur_in.pop_back();
is_asc = !is_asc;
}
for (int i = 0; i < tsub; i++) {
dsu.union_set(reps[LO[i]], subs[i]);
}
int minsz = INT_MAX;
FOR(i, 0, N) minsz = min(minsz, dsu.siz[dsu.find_set(i)]);
return minsz;
}
int min_cardinality(int N) {
default_random_engine rng;
INDICES.resize(N); iota(all(INDICES), 0); shuffle(all(INDICES), rng);
int ans = bsearch2(N);
// int ans = window(N);
// cout << "PUT: " << PUT_IN << " TAKE: " << TAKE_OUT << " PRESS: " << PRESS << "\n";
return ans;
}
