#include "mushrooms.h"
#include <bits/stdc++.h>
using namespace std;
vector<int> vec[2];
int count_mushrooms(int n)
{
if(n<3) return 2-use_machine({0, 1});
else
{
vec[0].push_back(0);
for(int i=1;i<3;i++) vec[use_machine({0, i})].push_back(i);
int s = vec[0].size();
int i=3;
for(;max(vec[0].size(), vec[1].size())<4&&i+1<n; i+=2)
{
int use = vec[0].size()>vec[1].size()?0:1;
int ans = use_machine({vec[use][0], i, vec[use][1], i+1});
if(ans>1) vec[!use].push_back(i);
else vec[use].push_back(i);
if(ans%2==0) vec[use].push_back(i+1);
else vec[!use].push_back(i+1);
if(use==0) s+= (4-ans)/2;
else s+= (ans+1)/2;
}
for(;max(vec[0].size(), vec[1].size())<100&&i+4<n; i+=5)
{
int use = vec[0].size()>vec[1].size()?0:1;
int ans_1;
vector<int> query_1;
for(int j=0; j<5; j++)
{
query_1.push_back(vec[use][j]);
query_1.push_back(i+j);
}
ans_1 = use_machine(query_1);
if(ans_1%2==0) vec[use].push_back(i+4); // last one is same
else vec[!use].push_back(i+4); // last one is NOT same
if(use==0) s+= (10-ans_1)/2;
else s+= (ans_1+1)/2;
if(ans_1<2) for(int j=0; j<4; j++) vec[use].push_back(i+j);
else if (ans_1>7) for(int j=0; j<4; j++) vec[!use].push_back(i+j);
else
{
int sim = ans_1/2;
int ans_2 = use_machine({vec[use][0], i, vec[use][1], i+1});
if(ans_2>1) vec[!use].push_back(i);
else vec[use].push_back(i);
if(ans_2%2==0) vec[use].push_back(i+1);
else vec[!use].push_back(i+1);
sim -= (ans_2+1)/2;
if(sim == 0)
{
vec[!use].push_back(i+2);
vec[!use].push_back(i+3);
}
else if(sim == 2)
{
vec[use].push_back(i+2);
vec[use].push_back(i+3);
}
else
{
int ans_3 = use_machine({vec[use][0], i+2, vec[use][1], i+3});
if(ans_3>1) vec[!use].push_back(i+2);
else vec[use].push_back(i+2);
if(ans_3%2==0) vec[use].push_back(i+3);
else vec[!use].push_back(i+3);
}
}
}
while(i<n)
{
int use = vec[0].size()>vec[1].size()?0:1;
vector<int> query;
for(auto it=vec[use].begin(); i<n&&it!=vec[use].end(); i++, it++)
{
query.push_back(*it);
query.push_back(i);
}
int ans = use_machine(query);
if(ans%2==0) vec[use].push_back(i-1); // last one is same
else vec[!use].push_back(i-1); // last one is NOT same
if(use==0) s+= (query.size()-ans)/2;
else s+= (ans+1)/2;
}
return s;
}
}
