#include "insects.h"
#include <bits/stdc++.h>
using namespace std;
using vi = vector<int>;
using ii = pair<int, int>;
bool gasit = false;
set<int> Cur;
vi Perm;
void movein2(int i) {
move_inside(Perm[i]);
}
void moveout2(int i) {
move_outside(Perm[i]);
}
vector<ii> cauta(vi Cul, vi V) {
vector<ii> Re;
if(gasit) return Re;
if(V.empty()) {
gasit = true;
return vector<ii>();
}
if(Cul.size() == 1) {
for(auto it : V) Re.push_back({it, Cul[0]});
return Re;
}
vi C1, C2;
for(int i = 0; i < int(Cul.size()) / 2; ++i) {
C1.push_back(Cul[i]);
}
for(int i = int(Cul.size()) / 2; i < int(Cul.size()); ++i) {
C2.push_back(Cul[i]);
}
set<int> SC1;
for(auto it : C1) SC1.insert(it);
vi de_scos;
for(auto it : Cur) {
if(!SC1.count(it))
de_scos.push_back(it);
}
for(auto it : de_scos) {
Cur.erase(it);
moveout2(it);
}
for(auto it : C1) {
if(!Cur.count(it)) {
movein2(it);
Cur.insert(it);
}
}
vi V1, V2;
for(auto it : V) {
movein2(it);
if(press_button() == 2) V1.push_back(it);
else V2.push_back(it);
moveout2(it);
}
// for(auto it : C1) {
// moveout2(it);
// }
auto Re1 = cauta(C1, V1), Re2 = cauta(C2, V2);
for(auto it : Re1) Re.push_back(it);
for(auto it : Re2) Re.push_back(it);
return Re;
}
int min_cardinality(int n) {
vi Cul, Rest;
Perm.clear();
for(int i = 0; i < n; ++i)
Perm.push_back(i);
mt19937 rng;
for(int i = 0; i < n; ++i) {
movein2(i);
if(press_button() == 1) {
Cur.insert(i);
Cul.push_back(i);
} else {
moveout2(i);
Rest.push_back(i);
}
}
if(Cul.size() > Rest.size()) return 1;
auto Per = cauta(Cul, Rest);
if(gasit) return 1;
map<int, int> Fr;
for(auto it : Cul) ++Fr[it];
for(auto [p, cul] : Per) ++Fr[cul];
int mi = n;
for(auto [cul, fr] : Fr) mi = min(mi, fr);
return mi;
}
