#include "mushrooms.h"
#include <bits/stdc++.h>
using namespace std;
const int M = 90;
int count_mushrooms(int n) {
if (n <= 226) {
int cnt = 0;
for (int i = 1; i < n; i++) {
if (use_machine({0, i})) continue;
cnt++;
}
return cnt+1;
}
vector<int> as, bs; as.push_back(0);
int a = use_machine({0, 1}), b = use_machine({0, 2});
int c, d, flp = 0;
if (!a && !b) {
c = 0, d = 1;
as.push_back(1);
as.push_back(2);
} else if (a && b) {
c = 1, d = 2; flp = 1;
bs.push_back(1);
bs.push_back(2);
} else {
if (a) {
c = 0;
d = 2;
bs.push_back(1);
as.push_back(2);
} else {
c = 0;
d = 1;
bs.push_back(2);
as.push_back(1);
}
}
int ans = 1 + (1 - a) + (1 - b);
int iter = min(n, M*2);
for (int i = 3; i < iter; i += 2) {
if (i >= iter) return ans;
vector<int> query;
query.push_back(c); query.push_back(i); query.push_back(d);
if (i < iter - 1) {
query.push_back(i + 1);
}
int k = use_machine(query);
if (k == 0) {
if (!flp) {
ans++;
as.push_back(i);
if (i < iter - 1) {
ans++;
as.push_back(i + 1);
}
} else {
bs.push_back(i);
if (i < iter - 1) bs.push_back(i + 1);
}
} else if (k == 1) {
if (!flp) {
as.push_back(i);
ans++;
if (i < iter - 1) bs.push_back(i + 1);
} else {
bs.push_back(i);
if (i < iter - 1) {
as.push_back(i + 1);
ans++;
}
}
} else if (k == 2) {
if (!flp) {
bs.push_back(i);
if (i < iter - 1) {
as.push_back(i + 1);
ans++;
}
} else {
as.push_back(i);
ans++;
if (i < iter - 1) bs.push_back(i + 1);
}
} else {
assert(k == 3);
if (!flp) {
bs.push_back(i);
if (i < iter - 1) bs.push_back(i + 1);
} else {
as.push_back(i);
ans++;
if (i < iter - 1) {
as.push_back(i + 1);
ans++;
}
}
}
}
vector<int> ps; bool flp2 = false;
if (as.size() > bs.size()) for (auto &x : as) ps.push_back(x);
else {
flp2 = true;
for (auto &x : bs) ps.push_back(x);
}
int c2 = 0;
for (int i = iter; i < n; ) {
bool curflp = false;
vector<int> *pool = &as;
if (bs.size() >= as.size()) {
curflp = true;
pool = &bs;
}
int take = min((int)pool->size(), n - i);
vector<int> qrs;
for (int j = 0; j < take; j++) {
qrs.push_back((*pool)[j]);
qrs.push_back(i + j);
}
int k = use_machine(qrs);
int used = take - 1;
if (curflp) {
c2 += k / 2;
} else {
c2 += used - k / 2;
}
int last = i + take - 1;
if (curflp) {
if (k % 2) as.push_back(last);
else bs.push_back(last);
} else {
if (k % 2) bs.push_back(last);
else as.push_back(last);
}
i += take;
}
return (int)as.size() + c2;
}
