#include "mushrooms.h"
#include <bits/stdc++.h>
using namespace std;
typedef vector<int> vi;
/*vi cur;
int use_machine(vi v) {
int ans = 0;
for (int i = 0; i<v.size()-1; ++i) if (cur[v[i]] != cur[v[i+1]]) ++ans;
return ans;
}*/
int queryOne(int ind) {
//return cur[ind];
return 1-use_machine(vi{0, ind});
}
int naive(int n) {
int ans = 0;
for (int i = 1; i<n; ++i) ans += queryOne(i);
return ans+1;
}
int count_mushrooms(int n) {
int k = 250;
if (n < k) return naive(n);
vi zeroes, ones = {0};
for (int i = 1; i<3; ++i) {
if (queryOne(i)) ones.push_back(i);
else zeroes.push_back(i);
}
bool AAA = ones.size() >= 2;
for (int i = 3; i<k; i += 2) {
if (AAA) {
int temp = use_machine({ones[0], i, ones[1], i+1});
if (temp % 2 == 1) zeroes.push_back(i+1);
else ones.push_back(i+1);
if (temp / 2 == 0) ones.push_back(i);
else zeroes.push_back(i);
}
else {
int temp = use_machine({zeroes[0], i, zeroes[1], i+1});
if (temp % 2 == 1) ones.push_back(i+1);
else zeroes.push_back(i+1);
if (temp / 2 == 0) zeroes.push_back(i);
else ones.push_back(i);
}
}
int ans = ones.size();
int curI = ones.size() + zeroes.size();
while (curI < n) {
bool useOne = ones.size() >= zeroes.size();
vi &equals = useOne ? ones : zeroes;
int advance = equals.size();
int maxi = curI + advance - 1;
if (maxi >= n) maxi = n-1, advance = maxi - curI + 1;
vi toUse;
for (int i = curI; i <= maxi; ++i) toUse.push_back(equals[i-curI]), toUse.push_back(i);
int temp = use_machine(toUse);
int maxiVal = temp & 1; temp = (temp+1)/2;
useOne ? ans += advance-temp : ans += temp;
curI = maxi+1;
maxiVal ? ones.push_back(maxi) : zeroes.push_back(maxi);
}
return ans;
}
/*
int main() {
for (int _ = 0; _ < 1000; ++_) {
int n = 5 + rand() % 20;
vi v(n, 1); for (int i = 1; i<n; ++i) v[i] = rand() % 2;
cur = v;
int val = count_mushrooms(n);
int real = accumulate(v.begin(), v.end(), 0);
if (val != real) {
cout << "a";
count_mushrooms(n);
}
}
}*/
/*
8
0 0 1 1 0 1 0 0
0 1 1 0 1 0 1 1
*/
