#include "insects.h"
#include "bits/stdc++.h"
#define SZ(s) ((int) s.size())
using namespace std;
#ifndef RR
#define DEBUG(X)
#endif
/*
int min_cardinality(int n) {
int res = n + 1; // final result
// used(i) = true if we already counted species of i
std::vector<bool> used(n, false);
for (int i = 0; i < n; ++i) {
if (!used[i]) {
// set containing all insects of this species
std::set<int> same_species {i};
move_inside(i);
for (int j = i + 1; j < n; ++j) {
if (!used[j]) {
move_inside(j);
if (press_button() == 1 + SZ(same_species)) {
same_species.insert(j);
} else {
move_outside(j);
}
}
}
res = std::min(res, SZ(same_species));
// remove all insects from machine
for (int j : same_species) {
move_outside(j);
used[j] = true;
}
}
}
return res;
}
*/
int min_cardinality(int n) {
std::set<int> insides; // set of insects inside machine
// lambda function to add one insect to machine
auto add = [&] (int i) { move_inside(i); insides.insert(i); };
// lambda function to remove one insect from machine
auto remove = [&] (int i) { move_outside(i); insides.erase(i); };
// lambda function to remove all insects from machine
auto reset_machine = [&] () { auto ids = insides; for (int i : ids) remove(i); };
// Step 1: Find set containing unique insects
for (int i = 0; i < n; ++i) {
add(i);
if (press_button() > 1) { // this species appeared before
remove(i);
}
}
int unique_vals = SZ(insides);
reset_machine();
// Step 2: Binary search for min f
int l = 2, r = n / unique_vals, res = 1;
while (l <= r) {
int mid = (l + r) / 2;
for (int i = 0; i < n; ++i) {
add(i);
if (press_button() > mid) remove(i);
}
int total = SZ(insides);
reset_machine();
if (total >= unique_vals * mid) {
res = mid;
l = mid + 1;
} else {
r = mid - 1;
}
}
return res;
}
