#include <bits/stdc++.h>
#include "mushrooms.h"
using namespace std;
const int SQ = 140;
int ask(vector<int> &v){
if((int) v.size() < 2) return 0;
return use_machine(v);
}
int solve(vector<int> &cur, vector<int> &a, vector<int> &b){
int cnt = 0;
vector<int> to_ask;
int sz_a = (int) a.size();
int sz = 0;
int l = 0;
while(!cur.empty() && l < (int) a.size() - 1){
to_ask.push_back(a[l++]);
to_ask.push_back(cur.back());
sz ++;
cur.pop_back();
}
if(l < (int) a.size()) to_ask.push_back(a[l++]);
int ans = ask(to_ask);
cnt += sz_a + (sz - (ans / 2));
sz = (int) cur.size();
to_ask.clear();
l = 0;
while(!cur.empty()){
to_ask.push_back(b[l++]);
to_ask.push_back(cur.back());
cur.pop_back();
}
if(l < (int) b.size()) to_ask.push_back(b[l++]);
ans = ask(to_ask);
cnt += ans / 2;
return cnt;
}
int count_mushrooms(int n){
vector<int> cur;
for(int i=1; i<n; i++) cur.push_back(i);
vector<int> a = {0}, b;
while(!cur.empty() && (int) a.size() + (int) b.size() < SQ + 2){
int v = cur.back();
cur.pop_back();
vector<int> to_ask = {0, v};
if(ask(to_ask) == 0){
a.push_back(v);
} else b.push_back(v);
}
vector<vector<int>> all_curs;
all_curs.push_back({});
int sz = (int) a.size() - 1 + (int) b.size() - 1;
for(auto x : cur){
if((int) all_curs.back().size() < sz){
all_curs.back().push_back(x);
} else all_curs.push_back({x});
}
int tot = 0;
for(auto cur : all_curs) tot += solve(cur, a, b);
return tot;
}
