#include "mushrooms.h"
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int inf = 1e9;
int use_machine(std::vector<int> x);
int count_mushrooms(int n) {
int mn = inf , cnt = 1;
for(int i = 1;i <= n; ++ i){
int cnt_query = 2 + (2 * i - 1 - 2 + 1) / 2 + ((n - 2 * i + 1) + i - 1) / i;
if(cnt_query < mn){
cnt = i;
mn = cnt_query;
}
}
//cout << mn << ' ';
int j = 1 , ans = 0;
vector<int> psa , psb;
psa.push_back(0);
while(true){
if(psa.size() >= 2 or psb.size() >= 2 or j >= n) break;
int nw = use_machine({0 , j});
if(nw) psb.push_back(j);
else psa.push_back(j);
j ++;
}
while(true){
if(psa.size() >= cnt or psb.size() >= cnt or j >= n) break;
int ps0 = 0 , ps1 = 0;
vector<int> qu;
if(psa.size() >= 2) ps0 = psa[0] , ps1 = psa[1];
else ps0 = psb[0] , ps1 = psb[1];
qu.push_back(j);
qu.push_back(ps0);
if(j + 1 < n){
qu.push_back(j + 1);
qu.push_back(ps1);
}
int val = use_machine(qu);
if(psa.size() < 2) val = 3 - val;
if(val & 1) psb.push_back(j);
else psa.push_back(j);
if((val & 2) and j + 1 < n) psb.push_back(j + 1);
else if(j + 1 < n) psa.push_back(j + 1);
j += 2;
}
ans += psa.size();
while(j < n){
vector<int> ps;
bool pa = true;
int msz = 0;
if(psa.size() >= psb.size()){
msz = psa.size();
for(auto to : psa) ps.push_back(to);
}
else{
pa = false;
msz = psb.size();
for(auto to : psb) ps.push_back(to);
}
int lps = j , c = 0;
vector<int> qu;
for(int i = j;i < min(n , j + msz); ++ i){
lps = i;
qu.push_back(ps[i - j]);
qu.push_back(i);
c ++;
}
j = min(n , j + msz);
//cout << c << ' ' << pa << '\n';
int k = use_machine(qu);
if(! pa){
ans += (k + 1) / 2;
if(k % 2 == 0) psb.push_back(lps);
else psa.push_back(lps);
}
else{
ans += (c - (k + 1) / 2);
if(k % 2 == 1) psb.push_back(lps);
else psa.push_back(lps);
}
}
return ans;
}
