#include "mushrooms.h"
#include <bits/stdc++.h>
using namespace std;
int count_mushrooms(int n) {
vector<int> m(4);
int c1 = use_machine({ 0, 1 });
if (n == 2){
if (c1){
return 1;
}
return 2;
}
int c2 = use_machine({ 0, 2 });
bool inverse = false;
long long int ret;
vector<int> Alar, Bler;
Alar.push_back(0);
if (c1 == 0)
Alar.push_back(1);
else
Bler.push_back(1);
if (c2 == 0)
Alar.push_back(2);
else
Bler.push_back(2);
if (c1 == 0){
m[0] = 0;
m[2] = 1;
}else if (c2 == 0){
m[0] = 0;
m[2] = 2;
}else{
inverse = true;
m[0] = 1;
m[2] = 2;
}
for (int i = 0; i < 80 && 4 + i * 2 < n; i++){
m[1] = 3 + i * 2;
m[3] = 4 + i * 2;
c2 = use_machine(m);
if (c2 & 1){
if (inverse)
Alar.push_back(4 + i * 2);
else
Bler.push_back(4 + i * 2);
}else{
if (inverse)
Bler.push_back(4 + i * 2);
else
Alar.push_back(4 + i * 2);
}
if (c2 >= 2){
if (inverse)
Alar.push_back(3 + i * 2);
else
Bler.push_back(3 + i * 2);
}else{
if (inverse)
Bler.push_back(3 + i * 2);
else
Alar.push_back(3 + i * 2);
}
}
int j = max(Alar.size(), Bler.size()) * 2;
vector<int> amac(j), bmac(j);
for (int i = 0; i < Alar.size(); i++){
amac[i * 2] = Alar[i];
}
for (int i = 0; i < Bler.size(); i++){
bmac[i * 2] = Bler[i];
}
ret = Alar.size();
j = Alar.size() + Bler.size();
int d = 0;
while (j + amac.size() / 2 < n){
for (int i = 0; i < amac.size() / 2; i++){
amac[i * 2 + 1] = j + i;
bmac[i * 2 + 1] = j + i;
}
d = amac.size() / 2;
if (Alar.size() >= Bler.size()){
c2 = use_machine(amac);
ret += amac.size() / 2 - (c2 + 1) / 2;
if (c2 & 1){
Bler.push_back(j + amac.size() / 2 - 1);
if (bmac.size() < Bler.size() * 2){
bmac.push_back(Bler.back());
bmac.push_back(0);
amac.push_back(0);
amac.push_back(0);
}else{
bmac[Bler.size() * 2 - 2] = Bler.back();
}
}else{
Alar.push_back(j + amac.size() / 2 - 1);
if (amac.size() < Alar.size() * 2){
amac.push_back(Alar.back());
amac.push_back(0);
bmac.push_back(0);
bmac.push_back(0);
}else{
amac[Alar.size() * 2 - 2] = Alar.back();
}
}
}else{
c2 = use_machine(bmac);
ret += (c2 + 1) / 2;
if (c2 & 1){
Alar.push_back(j + amac.size() / 2 - 1);
if (amac.size() < Alar.size() * 2){
amac.push_back(Alar.back());
amac.push_back(0);
bmac.push_back(0);
bmac.push_back(0);
}else{
amac[Alar.size() * 2 - 2] = Alar.back();
}
}else{
Bler.push_back(j + amac.size() / 2 - 1);
if (bmac.size() < Bler.size() * 2){
bmac.push_back(Bler.back());
bmac.push_back(0);
amac.push_back(0);
amac.push_back(0);
}else{
bmac[Bler.size() * 2 - 2] = Bler.back();
}
}
}
j += d;
}
if (n != j){
vector<int> son((n - j) * 2);
if (Alar.size() >= son.size() / 2){
for (int i = 0; i * 2 < son.size(); i++){
son[i * 2] = Alar[i];
son[i * 2 + 1] = j + i;
}
c2 = use_machine(son);
ret += son.size() / 2 - (c2 + 1) / 2;
}else{
for (int i = 0; i * 2 < son.size(); i++){
son[i * 2] = Bler[i];
son[i * 2 + 1] = j + i;
}
c2 = use_machine(son);
ret += (c2 + 1) / 2;
}
}
return ret;
}
