#include "light.h"
#include <vector>
#include <algorithm>
using namespace std;
static long long N;
static vector<long long> lit;
// Construye posiciones canonicas: n, n-1, n-3, n-7, n-15, ... (gaps 2^k - 1)
// Garantiza que la estructura permita alcanzar cualquier nuevo extremo con t <= p
vector<long long> canonical(long long n) {
vector<long long> res;
long long gap = 0, pw = 1;
while (n - gap >= 1 && (int)res.size() < 149) {
res.push_back(n - gap);
gap += pw;
pw *= 2;
}
// Asegurar que 1 este incluido
if (res.empty() || res.back() != 1) {
if (!res.empty() && res.back() > 1)
res.push_back(1);
else if (res.empty())
res.push_back(1);
}
sort(res.begin(), res.end());
res.erase(unique(res.begin(), res.end()), res.end());
return res;
}
// Construye intervalos merged de posiciones encendidas despues de spread t
vector<pair<long long,long long>> make_intervals(const vector<long long>& before, long long t, long long n) {
vector<pair<long long,long long>> intervals;
for (long long s : before) {
long long r = min(s + t, n);
intervals.push_back({s, r});
}
sort(intervals.begin(), intervals.end());
vector<pair<long long,long long>> merged;
for (auto& iv : intervals) {
if (!merged.empty() && iv.first <= merged.back().second + 1) {
merged.back().second = max(merged.back().second, iv.second);
} else {
merged.push_back(iv);
}
}
return merged;
}
// Verifica si pos esta en algun intervalo merged (busqueda binaria)
bool in_intervals(const vector<pair<long long,long long>>& ivs, long long pos) {
int lo = 0, hi = (int)ivs.size() - 1;
while (lo <= hi) {
int mid = (lo + hi) / 2;
if (ivs[mid].second < pos) lo = mid + 1;
else if (ivs[mid].first > pos) hi = mid - 1;
else return true;
}
return false;
}
void prepare() {
N = 1;
lit = {1};
}
pair<long long, vector<long long>> join(long long p) {
long long new_n = N + p;
// La antorcha en N alcanza new_n = N+p con t = p <= p_a
long long t = p;
N = new_n;
auto ivs = make_intervals(lit, t, N);
auto cand = canonical(N);
vector<long long> result;
for (long long pos : cand) {
if (in_intervals(ivs, pos))
result.push_back(pos);
}
// Asegurar que N (extremo derecho) este en el resultado
if (result.empty() || result.back() != N) {
result.push_back(N);
sort(result.begin(), result.end());
result.erase(unique(result.begin(), result.end()), result.end());
}
lit = result;
return {t, lit};
}
pair<long long, vector<long long>> leave(long long p) {
long long new_n = N - p;
// Filtrar antorchas que sobreviven (posicion <= new_n)
vector<long long> surviving;
for (long long pos : lit) {
if (pos <= new_n) surviving.push_back(pos);
}
// Calcular t minimo para encender new_n desde la antorcha sobreviviente mas a la derecha
// Prueba: con estructura canonica, t <= p siempre se cumple
// La antorcha en N-(2^k-1) con 2^k >= p+1 esta a distancia (2^k-1-p) <= p-1 de new_n
long long t = 0;
if (!surviving.empty()) {
long long rightmost_surv = surviving.back();
t = new_n - rightmost_surv;
} else {
// No deberia ocurrir si siempre guardamos posicion 1
// Forzar encendido desde 1
surviving = {1};
t = new_n - 1;
}
N = new_n;
auto ivs = make_intervals(surviving, t, N);
auto cand = canonical(N);
vector<long long> result;
for (long long pos : cand) {
if (in_intervals(ivs, pos))
result.push_back(pos);
}
// Asegurar N esta
if (result.empty() || result.back() != N) {
result.push_back(N);
sort(result.begin(), result.end());
result.erase(unique(result.begin(), result.end()), result.end());
}
lit = result;
return {t, lit};
}
