#include <bits/stdc++.h>
#include "mushrooms.h"
using namespace std;
using ll = long long;
const int maxN = 2e5 + 5;
const int MOD = 1e9 + 7;
vector<int> knownA , knownB, ask;
int cnt;
int query1(vector<int> a) {
int res = use_machine(a);
if(res == 1) {
knownB.push_back(a.back());
}
else {
knownA.push_back(a.back());
}
return res;
}
int query2(vector<int> a, bool type) {
int res = use_machine(a);
//cout << "type: " << type << endl;
if(((res & 2) == 2) == type) {
knownB.push_back(a[1]);
}
else {
knownA.push_back(a[1]);
}
if(((res & 1) == 1) == type) {
knownB.push_back(a.back());
}
else {
knownA.push_back(a.back());
}
return res;
}
int query3(vector<int> a, bool type) {
int res = use_machine(a);
if(type) {
cnt += (a.size() - res) / 2;
if(!(res % 2)) knownA.push_back(a.back());
else knownB.push_back(a.back());
}
else {
cnt += (res + 1) / 2;
if(res % 2) knownA.push_back(a.back());
else knownB.push_back(a.back());
}
return res;
}
int count_mushrooms(int n){
knownA.push_back(0);
ask = {0, 1};
int curr = 1;
// van legalabb 2
int res = query1(ask);
if(res == 1) {
ask[1] = 2;
query1(ask);
curr++;
}
int sq = sqrt(n);
//gyöknyi ugyanolyan keresese
while((int)knownA.size() < sq && (int)knownB.size() < sq) {
ask.clear();
bool type;
if(knownA.size() > 1) {
ask = {knownA[0], ++curr, knownA[1], ++curr};
type = 1;
}
else {
ask = {knownB[0], ++curr, knownB[1], ++curr};
type = 0;
}
query2(ask, type);
}
// megoldas
cnt = knownA.size();
while(curr < n) {
ask.clear();
bool type;
if(knownA.size() > knownB.size()) {
type = 1;
for(int i = 0; i < (int)knownA.size(); i++) {
ask.push_back(knownA[i]);
ask.push_back(++curr);
if(curr == n) break;
}
}
else {
type = 2;
for(int i = 0; i < (int)knownB.size(); i++) {
ask.push_back(knownB[i]);
ask.push_back(++curr);
if(curr == n) break;
}
}
query3(ask, type);
}
return cnt;
}
