#include "mushrooms.h"
#include <bits/stdc++.h>
using namespace std;
vector<int> vec[2];
pair<int, int> find_2(int i, bool add=true)
{
int use = vec[0].size()>vec[1].size()?0:1;
int ans = use_machine(vector<int>{vec[use][0], i, vec[use][1], i+1});
if(add)
{
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);
}
return {use, (ans+1)/2};
}
int count_mushrooms(int n)
{
if(n<3) return 2-use_machine({0, 1});
else
{
vec[0].push_back(0);
int i=1;
for(;i<3;i++) vec[use_machine({0, i})].push_back(i);
int s = vec[0].size();
for(;max(vec[0].size(), vec[1].size())<5&&i+1<n; i+=2)
{
auto res = find_2(i);
s += res.first==0?2-res.second:res.second;
}
for(;max(vec[0].size(), vec[1].size())<100&&i+4<n; i+=5)
{
int use = vec[0].size()>vec[1].size()?0: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);
}
int 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 dif = ans_1/2;
auto res = find_2(i);
dif -= res.first!=use?res.second:2-res.second;
if(dif == 0)
{
vec[use].push_back(i+2);
vec[use].push_back(i+3);
}
else if(dif == 2)
{
vec[!use].push_back(i+2);
vec[!use].push_back(i+3);
}
else find_2(i+2);
}
}
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;
}
}
