#include "mushrooms.h"
#include <bits/stdc++.h>
using namespace std;
template<class T, class U>
void ckmin(T &a, U b)
{
if (a > b) a = b;
}
template<class T, class U>
void ckmax(T &a, U b)
{
if (a < b) a = b;
}
#define MP make_pair
#define PB push_back
#define LB lower_bound
#define UB upper_bound
#define fi first
#define se second
#define FOR(i, a, b) for (auto i = (a); i < (b); i++)
#define FORD(i, a, b) for (auto i = (a) - 1; i >= (b); i--)
#define SZ(x) ((int) (x).size())
#define ALL(x) (x).begin(), (x).end()
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<pii> vpi;
typedef vector<pll> vpl;
int ask(vi v)
{
if (SZ(v) <= 1) return 0;
return use_machine(v);
}
int N, ans;
vi as, bs;
int count_mushrooms(int n)
{
N = n;
vi v(2);
v[0] = 0;
if (N < 10)
{
ans = 1;
FOR(i, 1, N)
{
v[1] = i;
int q = ask(v);
if (q != 1) ans++;
}
return ans;
}
as.PB(0);
FOR(i, 1, 4)
{
v[1] = i;
int q = ask(v);
if (q == 1)
{
bs.PB(i);
}
else
{
as.PB(i);
}
}
int MAGIC = 4, LIMIT = 85;
v.clear();
while(MAGIC + 1 < N && SZ(as) < LIMIT && SZ(bs) < LIMIT)
{
if (SZ(bs) >= 2)
{
v = {MAGIC, bs[0], MAGIC + 1, bs[1]};
int c = ask(v);
if (c == 0)
{
bs.PB(MAGIC);
bs.PB(MAGIC + 1);
}
if (c == 1)
{
as.PB(MAGIC);
bs.PB(MAGIC + 1);
}
if (c == 2)
{
bs.PB(MAGIC);
as.PB(MAGIC + 1);
}
if (c == 3)
{
as.PB(MAGIC);
as.PB(MAGIC + 1);
}
}
else
{
v = {MAGIC, as[0], MAGIC + 1, as[1]};
int c = ask(v);
if (c == 0)
{
as.PB(MAGIC);
as.PB(MAGIC + 1);
}
if (c == 1)
{
bs.PB(MAGIC);
as.PB(MAGIC + 1);
}
if (c == 2)
{
as.PB(MAGIC);
bs.PB(MAGIC + 1);
}
if (c == 3)
{
bs.PB(MAGIC);
bs.PB(MAGIC + 1);
}
}
MAGIC += 2;
}
ans = SZ(as);
if (SZ(bs) > SZ(as))
{
//we'll be counting how many bs there are in here.
while(MAGIC < N)
{
vi tmp = bs;
v.clear();
int lol = MAGIC;
v.PB(MAGIC);
v.PB(tmp.back());
tmp.pop_back();
MAGIC++;
while(MAGIC < N && !tmp.empty())
{
v.PB(MAGIC);
v.PB(tmp.back());
tmp.pop_back();
MAGIC++;
}
int c = ask(v);
ans += (c / 2) + (c % 2);
if (c % 2)
{
as.PB(lol);
}
else
{
bs.PB(lol);
}
}
}
else
{
while(MAGIC < N)
{
vi tmp = as;
v.clear();
v.PB(MAGIC);
int lol = MAGIC;
v.PB(tmp.back());
tmp.pop_back();
MAGIC++;
ans++;
while(MAGIC < N && !tmp.empty())
{
v.PB(MAGIC);
v.PB(tmp.back());
tmp.pop_back();
MAGIC++;
ans++;
}
int c = ask(v);
ans -= ((c / 2) + (c % 2));
if (c % 2)
{
bs.PB(lol);
}
else
{
as.PB(lol);
}
}
}
return ans;
// 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;
}
