#include <bits/stdc++.h>
#include "mushrooms.h"
template <class T> using Vec = std::vector<T>;
constexpr int NAIVE = 80;
int count_mushrooms(int n) {
Vec<int> a, b;
a.push_back(0);
for (int i = 1; i < std::min(n, NAIVE); ++i) {
(use_machine(Vec<int>{0, i}) ? b : a).push_back(i);
}
int ret = (int) a.size();
int seen = std::min(n, NAIVE);
while (seen < n) {
if (a.size() > b.size()) {
Vec<int> ask;
for (int i = 0; i < (int) a.size() and seen < n; ++i) {
ask.push_back(a[i]);
ask.push_back(seen++);
}
const auto rsp = use_machine(ask);
ret += (int) ask.size() / 2;
ret -= (rsp + 1) / 2;
(rsp % 2 == 0 ? a : b).push_back(ask.back());
} else {
Vec<int> ask;
for (int i = 0; i < (int) b.size() and seen < n; ++i) {
ask.push_back(b[i]);
ask.push_back(seen++);
}
const auto rsp = use_machine(ask);
ret += (rsp + 1) / 2;
(rsp % 2 == 0 ? b : a).push_back(ask.back());
}
}
return ret;
}
