#include "mushrooms.h"
#include <bits/stdc++.h>
using namespace std;
int count_mushrooms(int n) {
int b = max(3, (int) sqrt(n) + 20);
vector<int> ones;
vector<int> zeros = {0};
for (int i = 1; i < min(n, b); ++i) {
if (use_machine({0, i}) == 0) {
zeros.push_back(i);
} else {
ones.push_back(i);
}
}
int cnt = 0;
int p = b;
while (p < n) {
vector<int> ask;
int pv = 1;
if (ones.size() > zeros.size()) {
ask.push_back(ones[0]);
int oldp = p;
while (p < n && pv < (int) ones.size()) {
ask.push_back(p++);
ask.push_back(ones[pv++]);
}
int tmp = use_machine(ask) / 2;
if (tmp >= (int) ones.size() / 2) {
for (int i = oldp; i < p; ++i) {
if (use_machine({0, i}) == 0) {
zeros.push_back(i);
} else {
ones.push_back(i);
}
}
} else {
cnt += tmp;
}
} else {
ask.push_back(zeros[0]);
int tot = 0;
int oldp = p;
while (p < n && pv < (int) zeros.size()) {
ask.push_back(p++);
ask.push_back(zeros[pv++]);
tot += 2;
}
int tmp = use_machine(ask);
if ((tot - tmp) / 2 >= (int) zeros.size() / 2) {
for (int i = oldp; i < p; ++i) {
if (use_machine({0, i}) == 0) {
zeros.push_back(i);
} else {
ones.push_back(i);
}
}
} else {
cnt += (tot - tmp) / 2;
}
}
}
return zeros.size() + cnt;
}
