#include "mushrooms.h"
#include <bits/stdc++.h>
using namespace std;
const int K = 70;
int small(int n){
vector<int> m;
int ans = 1;
for (int i = 1; i < n; i++)
ans += (use_machine({0,i}) == 0);
return ans;
}
int count_mushrooms(int n) {
if(n <= 200){
return small(n);
}
bool type = 0;
vector<int> known,known_A,known_B;
int ind = 3;
int ans = 1;
// part one
bool sec = use_machine({0,1});
bool th = use_machine({0,2});
ans += (sec == 0) + (th == 0);
known_A.push_back(0);
if(sec == 0)known_A.push_back(1);
else known_B.push_back(1);
if(th == 0)known_A.push_back(2);
else known_B.push_back(2);
while(ind < n && known_A.size() < K && known_B.size() < K){
if(use_machine({0,ind}) == 0){
ans++;
known_A.push_back(ind);
}else{
known_B.push_back(ind);
}
ind++;
}
if(known_A >= known_B){
type = 0;
known = known_A;
}else{
type = 1;
known = known_B;
}
// part two
vector<int> m;
int i = 0;
while(ind < n){
if(i < (int)known.size()){
m.push_back(known[i]);
m.push_back(ind);
ind++;
i++;
}
if(i == (int)known.size() || ind == n){
int cnt = use_machine(m);
int elem = m.size();
if(!(cnt&1)){
known.push_back(m.back());
if(type == 0)ans++;
}else if(type)ans++;
cnt -= cnt&1;
elem-=2;
int kn = elem/2;
if(type){
ans += cnt/2;
}else ans += kn-(cnt/2);
m.clear();
i = 0;
}
}
return ans;
}
/*
21
0 1 1 1 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1
_ = A
_A 0
_B 1
_A_A 0
_A_B 1
_B_A 2
_B_B 3
_ = B
_A = 1
_B = 0
_B_B 0
_B_A 1
_A_B 2
_A_A 3
*/
