#include "mushrooms.h"
#include <bits/stdc++.h>
using namespace std;
const int needs = 125;
mt19937 rd(chrono::steady_clock::now().time_since_epoch().count());
int count_mushrooms(int n){
if (n <= 227){
int cntA = 1;
for (int i = 1; i < n; ++ i){
vector <int> ask = {0, i};
if (use_machine(ask) == 0) cntA ++;
}
return cntA;
}
vector <int> ord(n);
shuffle(ord.begin() + 1, ord.end(), rd);
auto qry = [&](vector <int> tmp) -> int {
vector <int> ask;
for (int i : tmp) ask.push_back(ord[i]);
return use_machine(ask);
};
vector <int> type(n, -1);
vector <int> cnt(2, 0);
vector <vector <int>> s(2);
auto fix = [&](int i, int t) -> void {
type[i] = t;
cnt[t] ++;
s[t].push_back(i);
};
fix(0, 0);
for (int c : {1, 2}){
vector <int> tmp = {0, c};
if (qry(tmp) == 0) fix(c, 0);
else fix(c, 1);
}
int cur = 0;
if (cnt[1] == 2) cur = 1;
int ptr = 3;
while (max(cnt[0], cnt[1]) < needs){
if (ptr == n - 1){
vector <int> tmp = {0, ptr};
if (qry(tmp) == 0) fix(ptr, 0);
else fix(ptr, 1);
return cnt[0];
}
vector <int> tmp = {s[cur][0], ptr, s[cur][1], ptr + 1};
int rt = qry(tmp);
fix(ptr + 1, cur ^ (rt & 1));
fix(ptr, cur ^ (rt > 1));
ptr += 2;
}
while (ptr < n){
int cur = 0;
if (s[1].size() > s[0].size()) cur = 1;
if (s[cur].size() > n - ptr){
vector <int> tmp = {s[cur][0]};
for (int i = ptr; i < n; ++ i){
tmp.push_back(i);
tmp.push_back(s[cur][i - ptr + 1]);
}
int rt = qry(tmp);
cnt[cur ^ 1] += rt / 2;
cnt[cur] += (n - ptr - rt / 2);
return cnt[0];
}
int siz = s[cur].size();
vector <int> tmp;
for (int i = 0; i < siz; ++ i){
tmp.push_back(s[cur][i]);
tmp.push_back(ptr + i);
}
int rt = qry(tmp);
fix(ptr + siz - 1, cur ^ (rt & 1));
cnt[cur ^ 1] += rt / 2;
cnt[cur] += (siz - 1 - rt / 2);
}
return cnt[0];
}
