#include<bits/stdc++.h>
#include "mushrooms.h"
using namespace std;
#define endl "\n"
typedef long long int ll;
const int MOD = 1e9 + 7;
//~ int use_machine(vector<int> x){
//~ cout << "Ask: ";
//~ for(int v : x) cout << v << " "; cout << endl;
//~ int rep; cin >> rep;
//~ return rep;
//~ }
int use_machine(vector<int> x);
int count_mushrooms(int n){
//Initially ask 73 questions.
vector<int> a = {0};
vector<int> b;
int ans = 1;
int rep = use_machine({0, 1});
if(rep == 1){
b.push_back(1);
}else {a.push_back(1); ans++;}
if(n == 2) return ans;
rep = use_machine({0, 2});
if(rep == 1){
b.push_back(2);
}else {a.push_back(2); ans++;}
int left = 72;
int curr = 3;
while(left > 0 && curr < n){
if(curr == n - 1){
rep = use_machine({0, curr});
if(rep == 0) ans++;
return ans;
}
if((int)a.size() >= 2){
rep = use_machine({0, curr, a[1], curr + 1});
if(rep >= 2) b.push_back(curr);
else {a.push_back(curr); ans++;}
if(rep % 2 == 1) b.push_back(curr + 1);
else {a.push_back(curr + 1); ans++;}
}else{
rep = use_machine({b[0], curr, b[1], curr + 1});
if(rep < 2) b.push_back(curr);
else {a.push_back(curr); ans++;}
if(rep % 2 == 0) b.push_back(curr + 1);
else {a.push_back(curr + 1); ans++;}
}
curr += 2;
left--;
}
while(curr < n){
if((int)a.size() < (int)b.size()){
vector<int> v;
for(int x : b){
v.push_back(x);
v.push_back(curr);
curr++;
if(curr == n) break;
}
rep = use_machine(v);
ans += rep / 2;
if(rep % 2 == 1) {ans++; a.push_back(v.back());}
}else{
vector<int> v;
int asked = 0;
for(int x : a){
v.push_back(x);
v.push_back(curr);
curr++;
asked++;
if(curr == n) break;
}
rep = use_machine(v);
ans += asked - rep / 2;
if(rep % 2 == 1) {ans--; b.push_back(v.back());}
}
}
return ans;
}
//~ int main(){
//~ int n; cin >> n;
//~ cout << count_mushrooms(n) << endl;
//~ }
