#include "mushrooms.h"
#include "bits/stdc++.h"
using namespace std;
#define pb push_back
#define sz(a) (int)a.size()
int count_mushrooms(int n) {
vector<int> a(n, -1);
a[0] = 0;
if(n <= 226) {
for(int i = 1; i < n; ++i) {
int x = use_machine({i - 1, i});
if(x) a[i] = !a[i - 1];
else a[i] = a[i - 1];
}
int ans = 0;
for(int i = 0; i < n; ++i) if(a[i] == 0) ++ans;
return ans;
}
vector<int> A;
vector<int> B;
A.pb(0);
int x = use_machine({0, 1});
if(x == 0) A.pb(1);
else B.pb(1);
x = use_machine({0, 2});
if(x == 0) A.pb(2);
else B.pb(2);
for(auto x: A) a[x] = 0;
for(auto x: B) a[x] = 1;
int limit = sqrt(n) * 2;
if(sz(A) >= 2) {
for(int i = 3; i + 1 < min(n, limit); i += 2) {
vector<int> v;
v.pb(A[0]);
v.pb(i);
v.pb(A[1]);
v.pb(i + 1);
int x = use_machine(v);
if(x & 2) {
B.pb(i);
} else A.pb(i);
if(x & 1) {
B.pb(i + 1);
} else A.pb(i + 1);
}
} else {
for(int i = 3; i + 1 < min(n, limit); i += 2) {
vector<int> v;
v.pb(B[0]);
v.pb(i);
v.pb(B[1]);
v.pb(i + 1);
int x = use_machine(v);
if(x & 2) {
A.pb(i);
} else B.pb(i);
if(x & 1) {
A.pb(i + 1);
} else B.pb(i + 1);
}
}
int cnt = 0;
for(auto x: A) {
++cnt;
a[x] = 0;
}
for(auto x: B) a[x] = 1;
vector<int> v;
for(int i = 0; i < n; ++i) {
if(a[i] == -1) v.pb(i);
}
if(sz(B) >= sz(A)) {
assert(sz(B) >= 1);
for(int i = 0; i < sz(v); i += sz(B)) {
vector<int> f;
int idx = 0;
for(int j = i; j < sz(v) && j < i + sz(B); ++j) {
f.pb(B[idx++]);
f.pb(v[j]);
}
int x = use_machine(f);
cnt += (x / 2) + (x % 2);
}
return cnt;
} else {
assert(sz(A) >= 1);
cnt += sz(v);
for(int i = 0; i < sz(v); i += sz(A)) {
vector<int> f;
int idx = 0;
for(int j = i; j < sz(v) && j < i + sz(A); ++j) {
f.pb(A[idx++]);
f.pb(v[j]);
}
int x = use_machine(f);
cnt -= (x / 2) + (x % 2);
}
return cnt;
}
}
