#include "mushrooms.h"
#include <bits/stdc++.h>
using namespace std;
typedef int ll;
typedef pair<ll, ll> pll;
#define vc vector
#define st first
#define nd second
#define all(a) a.begin(), a.end()
#define sz(a) (ll)a.size()
#define pub push_back
#define pob pop_back
ll count_mushrooms(ll n) {
vc<ll> a(n, -1);
a[0] = 0;
vc<ll> p(n);
iota(all(p), 0);
mt19937 rng(2137);
shuffle(++p.begin(), p.end(), rng);
const ll K = 3;
for (ll i = 0; i < n; i += K - 1) {
ll k = min(K, n - i);
vc<ll> q(k + 1);
for (ll l = k; l >= 2; l--) {
vc<ll> pos;
for (ll j = i; j < i + l; j++)
pos.pub(p[j]);
q[l] = use_machine(pos);
if (q[l] == 0) {
for (ll j = i + 1; j < i + l; j++)
a[p[j]] = a[p[j - 1]];
break;
} else if (q[l] == l - 1) {
for (ll j = i + 1; j < i + l; j++)
a[p[j]] = a[p[j - 1]] ^ 1;
break;
}
}
for (ll j = i + 1; j < i + k; j++) {
if (a[p[j]] == -1)
a[p[j]] = a[p[j - 1]] ^ (q[j - i + 1] - q[j - i]);
}
}
ll ret = 0;
for (ll &ai : a)
if (ai == 0)
ret++;
return ret;
}
