#include <bits/stdc++.h>
#include "mushrooms.h"
#pragma GCC optimize("Ofast")
#define x first
#define y second
#define ld long double
#define ll long long
using namespace std;
const int X = 146;
int q;
vector <bool> s;
vector <vector <int>> p(2);
/*int use_machine(vector <int> v) {
int ans = 0;
q++;
for(int i = 1; i < v.size(); i++)
ans += (s[v[i]] != s[v[i - 1]]);
return ans;
}*/
void add(int ind, int i, int &ans) {
ans += (ind == 0);
p[ind].push_back(i);
}
int count_mushrooms(int n) {
vector <int> q;
p[0].clear();
p[1].clear();
int x, ans = 1;
if(n <= X) {
for(int i = 1; i < n; i++) {
q.clear();
q.push_back(0), q.push_back(i);
x = use_machine(q);
ans += (x == 0);
}
return ans;
}
p[0].push_back(0);
for(int i = 1; i < 3; i++) {
q.clear();
q.push_back(0), q.push_back(i);
x = use_machine(q);
add(x, i, ans);
}
int a = (p[0].size() >= 2 ? 0 : 1), b = 1 - a;
for(int i = 3; i <= X; i += 2) {
q.clear();
q.push_back(i), q.push_back(p[a][0]), q.push_back(i + 1), q.push_back(p[a][1]);
x = use_machine(q);
if(x % 2 == 0)
add(a, i, ans);
else
add(b, i, ans);
if(x <= 1)
add(a, i + 1, ans);
else
add(b, i + 1, ans);
}
int i = X + 1;
while(i < n) {
a = (p[0].size() >= p[1].size() ? 0 : 1), b = 1 - a;
int lim = min(n - i, (int)p[a].size());
q.clear();
for(int j = 0; j < lim; j++)
q.push_back(i + j), q.push_back(p[a][j]);
x = use_machine(q);
if(x % 2 == 0)
p[a].push_back(i);
else
p[b].push_back(i);
i += lim;
if(a == 0) {
ans += lim - (x + 1) / 2;
} else {
ans += (x + 1) / 2;
}
}
return ans;
}
/*int main() {
int n, x;
cin >> n;
for(int i = 0; i < n; i++)
cin >> x, s.push_back(x);
cout << count_mushrooms(n);
cout << " with " << q << " queries used";
return 0;
}
*/
