// 80 points, q = 281
#include "mushrooms.h"
#include <bits/stdc++.h>
using namespace std;
// obs nova: a ideia de alternar do codigo pra 57 eh particularmente
// util quando k = 2:
// fazer a query [x A y A] ou [x B y B]
// me diz exatamente os valores de x e y:
// A A A A -> 0
// A A B A -> 2
// B A A A -> 1
// B A B A -> 3
// e para B
// A B A B -> 3
// A B B B -> 1
// B B A B -> 2
// B B B B -> 0
// passo 1:
// 2 queries pra saber 2 do mesmo tipo
// agora k - 2 queries pra saber k do mesmo tipo
// total: k queries
//
// passo 2:
// igual antes, (n - 2k + 1) / k queries
//
// agora minimizing k + (n - 2k + 1) / k
// minimizing k + n/k - 2
// minimizing k + n/k
// k = sqrt(n)
//
// k = 141
// 141 queries para descobrir 141 iguais entre os 281 primeiros
// agora sobraram (20000 - 281) / 141 ~ 140 queries pro resto
// 141 + 140 = 281 queries
int count_mushrooms(int n) {
if (n == 1) return 1;
vector<int> pos_A;
vector<int> pos_B;
pos_A.push_back(0);
if (use_machine({0, 1}) == 0) pos_A.push_back(1);
else pos_B.push_back(1);
if (use_machine({0, 2}) == 0) pos_A.push_back(2);
else pos_B.push_back(2);
int k = 141;
// passo 1
for (int i = 3; i < 2 * k - 1; i += 2) {
if (i == n) return ((int) pos_A.size());
if (i == n - 1) {
return ((int) pos_A.size()) + (1 - use_machine({0, i}));
}
if ((int) pos_A.size() >= 2) {
int ret = use_machine({i, pos_A[0], i+1, pos_A[1]});
if (ret == 0) {
pos_A.push_back(i);
pos_A.push_back(i+1);
} else if (ret == 1) {
pos_B.push_back(i);
pos_A.push_back(i+1);
} else if (ret == 2) {
pos_A.push_back(i);
pos_B.push_back(i+1);
} else {
pos_B.push_back(i);
pos_B.push_back(i+1);
}
} else {
int ret = use_machine({i, pos_B[0], i+1, pos_B[1]});
if (ret == 3) {
pos_A.push_back(i);
pos_A.push_back(i+1);
} else if (ret == 2) {
pos_B.push_back(i);
pos_A.push_back(i+1);
} else if (ret == 1) {
pos_A.push_back(i);
pos_B.push_back(i+1);
} else {
pos_B.push_back(i);
pos_B.push_back(i+1);
}
}
}
int step = pos_A.size();
bool using_b = false;
if (pos_A.size() < pos_B.size()) {
using_b = true;
step = pos_B.size();
}
// cout << "pos_A: ";
// for (int x: pos_A) {
// cout << x << " ";
// }
// cout << endl;
// cout << "pos_B: ";
// for (int x: pos_B) {
// cout << x << " ";
// }
// cout << endl;
// cout << "using_b = " << using_b << endl;
// cout << "step = " << step << endl;
int ans = pos_A.size();
int ini = 2 * k - 1;
while (ini < n) {
// ini x0 ini+1 x1 ini+2 x2 ... ini+step-1 xstep-1
// alternadamente
vector<int> aux;
int last = min(n - 1, ini + step - 1);
int cur_sz = last - ini + 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);
}
// cout << "will make query ";
// for (int x: aux) {
// cout << x << " ";
// }
// cout << endl;
int ret = use_machine(aux);
// cout << "got " << ret << endl;
if (using_b) {
ans += (ret + 1) / 2;
} else {
ans += cur_sz - (ret + 1) / 2;
}
ini += cur_sz;
// cout << "now ans = " << ans << endl;
// cout << "now ini = " << ini << endl;
}
return ans;
}
