#include "mushrooms.h"
#include <cassert>
int count_mushrooms(int n) {
if (n <= 227) {
int count = 1, cur = 0;
for (int i = 1; i < n; ++i) {
cur ^= (use_machine({i - 1, i}));
count += !cur;
}
return count;
}
std::vector<int> A = {0}, B;
int X = 201, reach = 0;
for (int i = 1; B.size() < 2 && i < X; i += 2) {
int y = use_machine({0, i, i + 1});
if (y == 0) {
A.push_back(i);
A.push_back(i + 1);
} else if (y == 2) {
B.push_back(i);
A.push_back(i + 1);
} else if (y == 1) {
if (use_machine({0, i})) {
B.push_back(i);
B.push_back(i + 1);
} else {
A.push_back(i);
B.push_back(i + 1);
}
} else
__builtin_unreachable();
reach = i + 1;
}
for (int i = reach + 1; i < X; i += 2) {
int y = use_machine({i, 0, B[0], i + 1, B[1]});
if (y == 1) {
A.push_back(i);
B.push_back(i + 1);
} else if (y == 2) {
B.push_back(i);
B.push_back(i + 1);
} else if (y == 3) {
A.push_back(i);
A.push_back(i + 1);
} else if (y == 4) {
B.push_back(i);
A.push_back(i + 1);
} else
__builtin_unreachable();
}
int count = A.size();
int amogus = std::max(A.size(), B.size());
int chosen = A.size() >= B.size() ? 0 : 1;
int l = X;
while (l < n) {
int r = std::min(n, l + amogus - 1) - 1;
std::vector<int> m;
if (0 == chosen) {
m = {A[0]};
for (int j = l, k = 1; j <= r; ++j, ++k) {
m.push_back(j);
m.push_back(A[k]);
}
count += (r - l + 1) - use_machine(m) / 2;
} else {
m = {B[0]};
for (int j = l, k = 1; j <= r; ++j, ++k) {
m.push_back(j);
m.push_back(B[k]);
}
count += use_machine(m) / 2;
}
l = r + 1;
}
return count;
}
