#include "mushrooms.h"
#include<bits/stdc++.h>
#define pb push_back
#define mp make_pair
#define vi vector<int>
#define f0r(i,n) for(int i = 0; i<n; i++)
#define FOR(i, k, n) for(int i = k; i<n; i++)
#define dout(x) cout<<x<<' '<<#x<<'\n';
#define vout(x) for(auto u : x)cout<<u<<' '; cout<<'\n';
#define vb vector<bool>
using namespace std;
int B = 145;
int count_mushrooms(int n) {
/*
std::vector<int> m;
for (int i = 0; i < n; i++)
m.push_back(i);
int c1 = use_machine(m);
m = {0, 1};
int c2 = use_machine(m);
return c1+c2;
*/
int mx = 1e9;
int mxd = 0;
for(int i = 1; i<=n; i++){
int cnt = i + (n - 2 * i + 1 + i - 1) / i;
if(cnt < mx){
mx = cnt;
mxd = i;
}
}
B = mxd;
vi as; vi bs;
as.pb(0);
int ret = use_machine({0, 1});
if(ret == 0){
as.pb(1);
}
else bs.pb(1);
if(n == 2)return as.size();
ret = use_machine({0,2});
if(ret == 0){
as.pb(2);
}
else bs.pb(2);
for(int i = 3; i<=B * 2 - 1; i+=2){
if(i + 1 >= n)break;
if(as.size() >= 2){
int ret = use_machine({as[0], i, as[1], i + 1});
if(ret == 3){
bs.pb(i);
bs.pb(i+1);
}
else if(ret == 2){
as.pb(i+1);
bs.pb(i);
}
else if(ret == 1){
as.pb(i);
bs.pb(i+1);
}
else{
as.pb(i); as.pb(i+1);
}
}
else{
int ret = use_machine({bs[0], i, bs[1], i+1});
if(ret == 3){
as.pb(i);
as.pb(i+1);
}
else if(ret == 2){
bs.pb(i+1);
as.pb(i);
}
else if(ret == 1){
bs.pb(i);
as.pb(i+1);
}
else{
bs.pb(i); bs.pb(i+1);
}
}
}
if(n <= B * 2 + 1){
if(n % 2 == 0){
int ret = use_machine({0, n-1});
if(ret == 0)as.pb(n-1);
else bs.pb(n-1);
}
return as.size();
}
else{
int ans = as.size();
// dout(ans);
int sz = max(as.size(), bs.size());
for(int i = B * 2 + 1; i < n; i += sz){
vi thing;
for(int j = i; j <= min(n-1, i + sz - 1); j++){
thing.pb(j);
}
if(as.size() > bs.size()){
vi quer;
int cnt = 0;
for(auto u : thing){
quer.pb(u);
quer.pb(as[cnt]);
cnt++;
}
int ret = use_machine(quer);
ans += thing.size() - ((ret / 2) + (ret % 2));
if(ret%2)bs.pb(thing[0]); else as.pb(thing[0]);
}
else{
vi quer;
int cnt = 0;
for(auto u : thing){
quer.pb(u);
quer.pb(bs[cnt]);
cnt++;
}
int ret = use_machine(quer);
ans += (ret / 2) + (ret % 2);
if(ret%2)as.pb(thing[0]); else bs.pb(thing[0]);
}
}
return ans;
}
return 0;
}
