// Solution by meowbert: see if this can improvement from 99.95 to 100
#include "insects.h"
#include <bits/stdc++.h>
using namespace std;
int min_cardinality(int N) {
vector<char> inside(N, false), banned(N, false);
vector<int> reps;
int species = 0;
for (int i = 0; i < N; ++i) {
move_inside(i);
inside[i] = true;
if (press_button() > 1) {
move_outside(i);
inside[i] = false;
} else {
++species;
reps.push_back(i);
}
}
vector<pair<int, int>> groups;
groups.reserve(species);
for (int i = 0; i < species; ++i) {
int left = reps[i] + 1;
int right = (i + 1 < species ? reps[i + 1] - 1 : N - 1);
groups.push_back({left, right});
}
int ans = 1;
int lo = 2;
int hi = N / species;
int last = 1;
vector<int> added;
while (lo <= hi) {
int tgt = lo + (hi - lo) / 2;
if (tgt < last) {
for (int i : added) {
move_outside(i);
inside[i] = false;
}
added.clear();
}
int need = species * (tgt - ans);
int remaining = 0;
for (int i = 0; i < N; ++i) {
if (!inside[i] && !banned[i]) {
++remaining;
}
}
vector<int> rejected;
vector<int> ptr(species);
for (int i = 0; i < species; ++i) {
ptr[i] = groups[i].first;
}
bool progressed = true;
while ((int)added.size() < need && progressed) {
if ((int)added.size() + remaining < need) {
break;
}
progressed = false;
for (int g = 0; g < species; ++g) {
int right = groups[g].second;
while (ptr[g] <= right && (inside[ptr[g]] || banned[ptr[g]])) {
++ptr[g];
}
if (ptr[g] > right) {
continue;
}
progressed = true;
int i = ptr[g]++;
--remaining;
move_inside(i);
inside[i] = true;
if (press_button() > tgt) {
move_outside(i);
inside[i] = false;
rejected.push_back(i);
} else {
added.push_back(i);
if ((int)added.size() == need) {
break;
}
}
if ((int)added.size() + remaining < need) {
break;
}
}
}
last = tgt;
if ((int)added.size() == need) {
ans = tgt;
lo = tgt + 1;
added.clear();
} else {
hi = tgt - 1;
for (int i : rejected) {
banned[i] = true;
}
}
}
return ans;
}
