#include "mushrooms.h"
#include<bits/stdc++.h>
using namespace std;
const unsigned int OPT = 80;
int ans;
vector<int> A, B;
queue<int> q;
int count_mushrooms(int n) {
vector<int> m;
A.push_back(0);
for(int i = 1; i < n; i++){
q.push(i);
}
while(q.size() && A.size() < 2 && B.size() < 2){
int c1 = q.front(); q.pop();
int verdic = use_machine({c1, A[0]});
if(verdic == 0) A.push_back(c1);
else B.push_back(c1);
}
while(q.size() && A.size() <= OPT && B.size() <= OPT){
int c1 = q.front(); q.pop();
if(q.empty()){
int verdic = use_machine({c1, A[0]});
if(verdic == 0) A.push_back(c1);
else B.push_back(c1);
break;
}
int c2 = q.front(); q.pop();
vector<int> *p1 = &A, *p2 = &B; // p1 aponta maior
if(p1->size() < p2->size()) swap(p1, p2);
vector<int> &v1 = *p1, &v2 = *p2; // v1 deve ser maior
int verdic = use_machine({v1[0], c1, v1[1], c2});
if(verdic == 0){
v1.push_back(c1);
v1.push_back(c2);
}
else if(verdic == 1){
v1.push_back(c1);
v2.push_back(c2);
}
else if(verdic == 2){
v2.push_back(c1);
v1.push_back(c2);
}
else{
v2.push_back(c1);
v2.push_back(c2);
}
}
while(!q.empty()){
if(A.size() < B.size()){ //use B
vector<int> m(min(2*B.size(), 2*q.size()));
for(int i = 0; i < (int)m.size(); i+=2) m[i] = B[i/2];
for(int i = 1; i < (int)m.size(); i+=2){
m[i] = q.front(); q.pop();
}
int verdic = use_machine(m);
ans += (verdic+1)/2;
if(verdic&1){
ans--;
A.push_back(m.back());
}
else B.push_back(m.back());
}
else{
vector<int> m(min(2*A.size(), 2*q.size()));
for(int i = 0; i < (int)m.size(); i+=2) m[i] = A[i/2];
for(int i = 1; i < (int)m.size(); i+=2){
m[i] = q.front(); q.pop();
}
int verdic = use_machine(m);
ans += m.size()/2-(verdic+1)/2;
if(verdic&1) B.push_back(m.back());
else{
ans--;
A.push_back(m.back());
}
}
}
return A.size()+ans;
}
