#include "mushrooms.h"
#include <bits/stdc++.h>
using namespace std;
#define sz(v) (int)(v).size()
const int SQRT = 140;
int count_mushrooms(int n) {
vector<int> a{0}, b;
vector<int> query; int pt = 1;
for (int it=0; it<81 and sz(a) + sz(b) < n; it++, pt+=2) {
query.clear();
if (sz(a) + sz(b) == n-1) {
query = vector<int> {a[0], pt};
int res = use_machine(query);
if (res == 0) a.push_back(pt);
else b.push_back(pt);
pt++;
break;
}
if (sz(a) >= 2) {
query = vector<int> {a[0], pt, a[1], pt+1};
int res = use_machine(query);
if (res == 0 or res == 1) a.push_back(pt);
else b.push_back(pt);
if (res == 0 or res == 2) a.push_back(pt+1);
else b.push_back(pt+1);
continue;
}
query = vector<int>{pt, a[0], pt+1};
int res = use_machine(query);
if (res == 0) {
a.push_back(pt);
a.push_back(pt+1);
} else if (res == 2) {
b.push_back(pt);
b.push_back(pt+1);
} else {
query = vector<int> {pt, a[0]};
res = use_machine(query);
if (res == 0) {
a.push_back(pt);
b.push_back(pt+1);
} else {
b.push_back(pt);
a.push_back(pt+1);
}
}
}
int ans = sz(a);
while (pt < n) {
bool aBetween = false;
vector<int> query;
int qty = 0;
if (sz(a) >= sz(b)) {
for (int i=0; i<sz(a) and pt < n; i++, pt++) {
query.push_back(a[i]);
query.push_back(pt);
qty++;
}
aBetween = true;
} else {
for (int i=0; i<sz(b) and pt < n; i++, pt++) {
query.push_back(b[i]);
query.push_back(pt);
qty++;
}
aBetween = false;
}
int res = use_machine(query);
if ((res & 1) == aBetween) b.push_back(pt-1);
else a.push_back(pt-1);
res -= (res & 1);
ans += (aBetween ? qty - res / 2 : res / 2);
}
return ans;
}
