// 92 points, q = 245
#include "mushrooms.h"
#include <bits/stdc++.h>
using namespace std;
// alguma informacao que ainda nao estamos usando?
// - de que nossas queries do passo 2 tem todos os elementos conhecidos iguais
// - entao, paridade determina o valor do primeiro desconhecido
// - isso quer dizer que cada query do passo 2 contribui em 1
// para os sets do passo 1
// entao vamos usar:
// - passo 1: k queries para encontrar k iguais, como antes
// - passo 2: vamos sempre usando o maior set e atualizando os sets
// total de caras novos descobertos a cada passo vai aumentando
// k, k+1, k+1, k+2, k+2, ..., s, s
// se no final o tamanho do set é s, eu tenho
//
// total de posicoes contadas:
// (2k - 1) + 2k + 2(k+1) + 2*(k+2) + ... + 2s
//
// quero
// (2k - 1) + 2k + 2(k+1) + 2*(k+2) + ... + 2s >= n
// 1 + 2*((k-1) + k + k+1 + ... + s) >= n
// 2 * soma(k-1, s) >= n
// s * (s + 1) - (k - 2) * (k - 1) >= n
// arredonda pra
// s^2 - (k - 1)^2 >= n
//
// (s - k) * (s + k) >= n
//
// numero de queries: k + 2 * (s - k) - 1 = 2s + k - 1
// queremos 2s + k - 1 <= 226
// s precisa ser > 100
// vamos chutar s = 105:
// posso fazer k = 33
// fica 210 + 33 - 1 = 245 queries
//
// parece que nao da pra melhorar muito de 245
//
//
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 (n == 2) return ((int) pos_A.size());
if (use_machine({0, 2}) == 0) pos_A.push_back(2);
else pos_B.push_back(2);
int k = 36;
// 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;
if (ret % 2 == 0) {
pos_B.push_back(ini);
} else {
pos_A.push_back(ini);
}
} else {
ans += cur_sz - (ret + 1) / 2;
if (ret % 2 == 0) {
pos_A.push_back(ini);
} else {
pos_B.push_back(ini);
}
}
ini += cur_sz;
// cout << "now ans = " << ans << endl;
// cout << "now ini = " << ini << endl;
step = pos_A.size();
using_b = false;
if (pos_A.size() < pos_B.size()) {
using_b = true;
step = pos_B.size();
}
}
return ans;
}
| # | Verdict | Execution time | Memory | Grader output |
|---|
| Fetching results... |
