#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 = 100;
if (n < k) return naive(n);
vi zeroes, ones = {0};
for (int i = 1; i<k; ++i) {
if (queryOne(i)) ones.push_back(i);
else zeroes.push_back(i);
if (max(ones.size(), zeroes.size()) == 100) break;
}
int ans = ones.size();
bool useOne = ones.size() >= zeroes.size();
vi &equals = useOne ? ones : zeroes;
int curI = ones.size() + zeroes.size();
while (curI < n) {
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)+1)/2;
useOne ? ans += advance-temp : ans += temp;
curI = maxi+1;
}
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
*/
