#include<bits/stdc++.h>
#include "mushrooms.h"
using namespace std;
constexpr int maxk = 90;
vector <int> sure[2];
int res = 0;
void debug()
{
for (int i : sure[0])
cout << i << " ";
cout << "\n";
for (int i : sure[1])
cout << i << " ";
cout << "\n";
cout << "-----------------\n";
}
void first_two()
{
vector<int> arr;
arr.push_back(0);
arr.push_back(1);
int curr = use_machine(arr);
if (curr == 0){
sure[0].push_back(1);
return;
}
sure[1].push_back(1);
arr.pop_back();
arr.push_back(2);
curr = use_machine(arr);
sure[curr].push_back(2);
while (arr.size())
arr.pop_back();
}
void phase1(int k)
{
vector<int> arr = {0, 0, 0, 0};
int counter = (int)sure[0].size() + (int)sure[1].size();
int which = (sure[0].size() >= 2 ? 0 : 1);
while ((int)sure[0].size() < k && (int)sure[1].size() < k)
{
arr[0] = sure[which][0], arr[1] = counter, arr[2] = sure[which][1], arr[3] = counter + 1;
int curr = use_machine(arr);
sure[(which ^ (curr % 2))].push_back(counter + 1);
curr /= 2;
sure[(which ^ curr)].push_back(counter);
counter += 2;
}
}
void phase2(int n)
{
int counter = (int)sure[0].size() + (int)sure[1].size();
int which = (sure[0].size() >= sure[1].size() ? 0 : 1);
while (counter < n)
{
int siz = min(n - counter, (int)sure[which].size());
vector <int> arr;
for (int i = 0; i < siz; i++){
arr.push_back(sure[which][i]);
arr.push_back(counter + i);
}
int curr = use_machine(arr);
sure[(which ^ (curr % 2))].push_back(counter + siz - 1);
res += (which == 0 ? siz - curr / 2 - 1 : curr/2);
which = (sure[0].size() >= sure[1].size() ? 0 : 1);
//while (arr.size()) arr.pop_back();
counter += siz;
}
res += (int)sure[0].size();
}
int count_mushrooms(int n)
{
// corner case
if (n == 2){
vector <int> arr = {0, 1};
int curr = use_machine(arr);
if (curr == 0)
curr = 2;
return curr;
}
sure[0].push_back(0);
first_two();
// already know at least 2 of same kind
//debug();
phase1(min(n/2 - 1, maxk));
//debug();
// already know at leat k of same kind
phase2(n);
//debug();
return res;
}
/*
10
0 0 0 0 0 0 0 0 0 1
*/
