#include <iostream>
#include <vector>
#include "mushrooms.h"
using namespace std;
vector<int> v1 = {0}, v2;
int count_mushrooms(int n){
if (n <= 226){
int A = 1;
for (int i=1;i<n;i++)
A += !use_machine({0, i});
return A;
}
for (int i : {1, 2}){
if (use_machine({0, i}) == 0)
v1.push_back(i);
else
v2.push_back(i);
}
int L = 3;
for (int i=3;i < n and i<175;i+=2){
if (i + 1 == n){
if (use_machine({0, i}))
v2.push_back(i);
else
v1.push_back(i);
}
else if (v1.size() > 1){
int x = use_machine({i, v1[0], i+1, v1[1]});
if ((x & 1) == 0)
v1.push_back(i);
else
v2.push_back(i);
if ((x & 2) == 0)
v1.push_back(i+1);
else
v2.push_back(i+1);
}
else{
int x = use_machine({i, v2[0], i+1, v2[1]});
if ((x & 1) == 0)
v2.push_back(i);
else
v1.push_back(i);
if ((x & 2) == 0)
v2.push_back(i+1);
else
v1.push_back(i+1);
}
L = i + 2;
}
int A = v1.size(), B = v2.size();
for (int i=L;i<n;){
int k = 0;
if (v1.size() > v2.size()){
vector<int> v;
for (int j=1;i+j <= n and j < v1.size();j++){
v.push_back(i+j-1);
v.push_back(v1[j]);
k++;
}
int x = use_machine(v);
if (x & 1)
v2.push_back(v[0]);
else
v1.push_back(v[0]);
x += x & 1;
A += k - x / 2;
}
else{
vector<int> v;
for (int j=1;i+j <= n and j < v2.size();j++){
v.push_back(i+j-1);
v.push_back(v2[j]);
k++;
}
int x = use_machine(v);
if (x & 1)
v1.push_back(v[0]);
else
v2.push_back(v[0]);
x += x & 1;
A += x / 2;
}
i += k;
}
return A;
}
