#include "prize.h"
#include <vector>
using namespace std;
vector<pair<int, int>> preguntasHechas;
int totalInteresantes;
pair<int, int> preguntar(int i) {
if (preguntasHechas[i].first == -1) {
auto a = ask(i);
return preguntasHechas[i] = make_pair(a[0], a[1]);
}
return preguntasHechas[i];
}
int carosIzq(int i) {
pair<int, int> v = preguntar(i);
return v.first;
}
int carosDer(int i) {
pair<int, int> v = preguntar(i);
return v.second;
}
// limIzq contendrá lollipop
// buscamos el diamante en [limIzq, limDer]
// sabemos que en el intervalo hay numPremiosCaros (i.e. premios no lollipop)
int buscarDiamanteEnIntervalo(int limIzq, int limDer, int numPremiosCaros) {
if (!numPremiosCaros) return -1;
if (limDer-limIzq == numPremiosCaros) {
// todas las posiciones aparte de limIzq contienen premio caro -> buscamos una a una por el diamante
for (int i = limIzq+1; i <= limDer; i++) {
preguntar(i);
if (carosIzq(i) + carosDer(i) == 0) {
return i;
}
}
return -1;
}
int mid = limIzq + (limDer-limIzq)/2;
int pos = mid;
while(pos <= limDer) {
if (carosIzq(pos) + carosDer(pos) == 0) {
return pos;
}
if (carosIzq(pos) + carosDer(pos) == totalInteresantes) {
break;
}
pos++;
}
if (pos == limDer+1) {
// no hay lollipops en [mid, limDer]
return buscarDiamanteEnIntervalo(limIzq, mid-1, numPremiosCaros - (limDer - mid + 1));
} else {
int diamante = buscarDiamanteEnIntervalo(limIzq, mid-1, carosIzq(pos) - carosIzq(limIzq) + mid - pos);
if (diamante != -1) return diamante;
return buscarDiamanteEnIntervalo(pos, limDer, numPremiosCaros - carosIzq(pos) + carosIzq(limIzq));
}
}
int find_best(int n) {
preguntasHechas.assign(n, make_pair(-1, -1));
// buscamos el índice del primer lollipop
int primerLollipop = 0;
totalInteresantes = -1;
for (int i = 0; i < min(473, n); i++) {
if (carosIzq(i) + carosDer(i) == 0) return i;
if (carosIzq(i) + carosDer(i) > totalInteresantes) {
primerLollipop = i;
totalInteresantes = carosIzq(i) + carosDer(i);
}
if (totalInteresantes >= 40) break;
}
return buscarDiamanteEnIntervalo(primerLollipop, n-1, carosDer(primerLollipop));
}
