#include "mushrooms.h"
#include <bits/stdc++.h>
using namespace std;
#define lli int
#define rep(i,a,b) for(int i = (a); i <= (b); i++)
#define repa(i,a,b) for(int i = (a); i >= (b); i--)
#define debug(a) cout << #a << " = " << a << endl
#define debugsl(a) cout << #a << " = " << a << ", "
lli as,bs,pos,p,tam,y,res;
vector<lli> A,B,arr,ult;
lli busca(lli raiz, lli tipo) {
vector<lli> llamada;
llamada = vector<lli> (4, 0);
if (tipo == 1) llamada[0] = A[0], llamada[2] = A[1];
else llamada[0] = B[0], llamada[2] = B[1];
lli x,pos = 3;
while (as < raiz && bs < raiz) {
llamada[1] = pos++;
llamada[3] = pos++;
x = use_machine(llamada);
if (tipo == 1) {
if (x == 0) {as += 2; A.push_back(pos-2); A.push_back(pos-1);}
else if (x == 1) {as++; A.push_back(pos-2); bs++; B.push_back(pos-1);}
else if (x == 2) {as++; A.push_back(pos-1); bs++; B.push_back(pos-2);}
else {bs += 2; B.push_back(pos-2); B.push_back(pos-1);}
}
else {
if (x == 0) {bs += 2; B.push_back(pos-2); B.push_back(pos-1);}
else if (x == 1) {as++; A.push_back(pos-1); bs++; B.push_back(pos-2);}
else if (x == 2) {as++; A.push_back(pos-2); bs++; B.push_back(pos-1);}
else {as += 2; A.push_back(pos-2); A.push_back(pos-1);}
}
}
if (as > bs) return 1;
else return 2;
}
int count_mushrooms(int n) {
as = 1;
bs = 0;
if (n == 2) {
p = use_machine({0,1});
if (p == 1) return 1;
else return 2;
}
p = use_machine({0,1});
if (p == 0) A.push_back(1), as++;
else B.push_back(1), bs++;
p = use_machine({0,2});
if (p == 0) A.push_back(2), as++;
else B.push_back(2), bs++;
p = sqrt(n);
p++;
if (as >= 2) p = busca(p,1);
else p = busca(p,2);
if (p == 1) {
arr.resize(as*2);
lli pos = 0;
for(auto act : A) {arr[pos] = act; pos += 2;}
//rep(i,0,(as*2)-1) cout << arr[i] << ' ';
}
else {
arr.resize(bs*2);
lli pos = 0;
for(auto act : B) {arr[pos] = act; pos += 2;}
//rep(i,0,(bs*2)-1) cout << arr[i] << ' ';
}
//cout << endl;
pos = as+bs;
res = as;
while (pos < n) {
if (p == 1) {
if (n-pos < as) break;
y = 1;
rep(i,0,as-1) {arr[y] = pos++; y+=2;}
y = use_machine(arr);
y++;
y/=2;
y = as-y;
res += y;
}
else {
if (n-pos < bs) break;
y = 1;
rep(i,0,bs-1) {arr[y] = pos++; y+=2;}
y = use_machine(arr);
y++;
y/=2;
res += y;
}
}
if (pos < n) {
ult.resize((n-pos)*2);
y = pos;
rep(i,0,((n-pos)*2)-1) {
if ((i%2) == 0) ult[i] = arr[i];
else {
ult[i] = y;
y++;
}
}
y = use_machine(ult);
y++;
y /= 2;
if (p == 1) y = (n-pos)-y;
res += y;
}
return res;
}
