// 57 points, q = 397
#include "mushrooms.h"
#include <bits/stdc++.h>
using namespace std;
// ideias:
// - encontrar um conjunto de caras com mesmo valor
// - usar eles como "separadores" para contar desconhecidos
//
// passo 1:
// 2k - 2 queries [0, i] para encontrar k iguais
// entre os 2k - 1 primeiros
//
// passo 2:
// agora sobraram n - 2k + 1 ainda pra contar
// #queries adicionais = teto( (n - 2k + 1) / k )
//
// otimizacao:
// minimize 2k - 2 + (n - 2k + 1) / k
// = 2k + (n + 1)/k - 4
// ~ 2k + n/k
//
// minimize 2k + n/k
// 2k = n/k
// k = sqrt(n / 2)
// k = 100
//
// total:
// 198 queries para encontrar 100 iguais entre os 199 primeiros
// teto[(20000 - 199) / 100] = 199 queries pro resto
// 198 + 199 = 397 queries
int count_mushrooms(int n) {
if (n == 1) return 1;
vector<int> pos_A;
vector<int> pos_B;
pos_A.push_back(0);
int k = 100;
// passo 1
for (int i = 1; i < min(n, 2 * k - 1); i++) {
if (use_machine({0, i}) == 0) pos_A.push_back(i);
else pos_B.push_back(i);
}
int step = pos_A.size();
bool using_b = false;
if (pos_A.size() < pos_B.size()) {
using_b = true;
step = pos_B.size();
}
int ans = pos_A.size();
if (2 * k - 1 >= n) return ans;
for (int ini = 2 * k - 1; ini < n; ini += step) {
// ini x0 ini+1 x1 ini+2 x2 ... ini+step-1 xstep-1
// alternadamente
vector<int> aux;
int l = ini, r = min(n - 1, ini + step - 1);
int cur_sz = r - l + 1;
for (int j = 0; j < cur_sz; j++) {
aux.push_back({ini + j});
int pos_to_use = using_b ? pos_B[j] : pos_A[j];
aux.push_back(pos_to_use);
}
int ret = use_machine(aux);
if (using_b) {
ans += ret;
} else {
ans += cur_sz - ret;
}
}
return ans;
}
