#include "mushrooms.h"
#include <bits/stdc++.h>
using namespace std;
vector<int> build(vector<int> a, vector<int> b) {
reverse(a.begin(), a.end());
reverse(b.begin(), b.end());
vector<int> fin;
while (a.size() || b.size()) {
if (!a.empty()) {
fin.push_back(a.back());
a.pop_back();
}
if (!b.empty()) {
fin.push_back(b.back());
b.pop_back();
}
}
return fin;
}
int count_mushrooms(int n) {
vector<int> inA, inB;
inA.push_back(0);
int ans = 1;
for (int i = 1; i < n; i++) {
vector<int> qr;
if (inA.size() >= inB.size()) qr = inA;
else qr = inB;
int willGet = qr.size();
vector<int> toDo;
for (int j = i; j < min(n, i + willGet); j++) {
toDo.push_back(j);
}
vector<int> asks = build(qr, toDo);
int tot = use_machine(asks);
if (inA.size() >= inB.size()) {
int totB = tot / 2;
if (qr.size() == toDo.size()) {
if (tot & 1) {
inB.push_back(toDo.back());
totB++;
}
else {
inA.push_back(toDo.back());
}
}
ans += ((int)toDo.size() - totB);
}
else {
ans += tot / 2;
if (qr.size() == toDo.size()) {
if (tot & 1) {
inA.push_back(toDo.back());
ans++;
}
else {
inB.push_back(toDo.back());
}
}
}
i = i + willGet - 1;
}
return ans;
}
