#include "light.h"
#include <vector>
#include <algorithm>
using namespace std;
typedef long long ll;
// Variables globales para mantener el estado
ll current_L = 1;
vector<ll> torches;
/**
* Se llama al inicio. Inicializamos con la primera antorcha en la posición 1.
*/
void prepare() {
current_L = 1;
torches = {1};
}
/**
* Función auxiliar para mantener el número de antorchas por debajo de 150.
* Elimina las antorchas que tienen los saltos proporcionales más pequeños.
*/
void prune() {
while (torches.size() > 150) {
int best_idx = -1;
double min_ratio = 1e18;
// No eliminamos ni la primera (1) ni la última (el extremo derecho actual)
for (int i = 1; i < (int)torches.size() - 1; ++i) {
// Evaluamos la relación entre la siguiente y la anterior
double ratio = (double)torches[i + 1] / torches[i - 1];
if (ratio < min_ratio) {
min_ratio = ratio;
best_idx = i;
}
}
if (best_idx != -1) {
torches.erase(torches.begin() + best_idx);
}
}
}
/**
* Cuando p personas se unen por la derecha.
*/
pair<ll, vector<ll>> join(ll p) {
ll ta = p; // Usamos el máximo permitido para facilitar el encendido
current_L += p;
// Añadimos la nueva posición final a nuestras antorchas
torches.push_back(current_L);
// Limpiamos para no pasarnos de 150
prune();
return {ta, torches};
}
/**
* Cuando p personas se van por la derecha.
*/
pair<ll, vector<ll>> leave(ll p) {
current_L -= p;
// Eliminamos de nuestra lista las antorchas que ya no están en el escenario
while (!torches.empty() && torches.back() > current_L) {
torches.pop_back();
}
ll ta = 0;
// Si la nueva posición final no tiene antorcha, la encendemos desde la anterior
if (torches.empty() || torches.back() < current_L) {
if (torches.empty()) {
ta = current_L;
} else {
ta = current_L - torches.back();
}
torches.push_back(current_L);
}
// Volvemos a podar para mantener el límite
prune();
return {ta, torches};
}
