Submission #1329411

#	Time	Username	Problem	Language	Result	Execution time	Memory
1329411		jochis	A Light Inconvenience (CEOI23_light)	C++20	Compilation error	0 ms	0 KiB

light

#include "light.h"
#include <vector>
#include <set>
#include <algorithm>
using namespace std;

static long long N;
static vector<long long> lit; // posiciones encendidas, ordenadas

// Construye posiciones canónicas: n, n-1, n-3, n-7, ... (gaps 2^k-1)
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;
    }
    if (res.empty() || res.back() != 1) {
        // agregar 1 si no está
        if (res.back() > 1) res.push_back(1);
    }
    sort(res.begin(), res.end());
    res.erase(unique(res.begin(), res.end()), res.end());
    return res;
}

// Dada la lista de antorchas 'before' (antes del t), y aplicando spread t,
// retorna el conjunto de posiciones encendidas en [1, n]
// = union de intervalos [s, s+t] intersectado [1,n]
vector<long long> spread(const vector<long long>& before, long long t, long long n) {
    // Merge intervals
    vector<pair<long long,long long>> intervals;
    for (long long s : before) {
        intervals.push_back({s, min(s + t, n)});
    }
    // Merge
    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);
        }
    }
    // Expandir (demasiados puntos, solo nos interesa si la posición deseada está)
    // No expandimos; solo verificamos membresía
    // Retornamos merged como estructura
    // Para nuestro uso, queremos saber si 'pos' está encendida:
    // pos está en algún [a,b] merged
    // Retornamos los merged intervals
    // Pero la firma dice vector<long long>... retornemos solo los extremos relevantes
    // En realidad para este problema no necesitamos expandir,
    // solo verificar que las posiciones en 'desired' están encendidas
    vector<long long> dummy;
    return dummy; // placeholder
}

// Verifica si 'pos' está en alguno de los intervalos merged
bool in_intervals(const vector<pair<long long,long long>>& ivs, long long pos) {
    // binary search
    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;
}

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 l = s; // s pasa fuego hacia la derecha, entonces enciende [s, s+t]
        // Pero también: performer i se enciende si algún j en [i-t, i] estaba encendido
        // = hay j en before con s = j y j >= i - t, j <= i
        // = i en [s, s+t]
        long long r = min(s + t, n);
        intervals.push_back({l, 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;
}

void prepare() {
    N = 1;
    lit = {1};
}

pair<long long, vector<long long>> join(long long p) {
    long long new_n = N + p;
    // Antorcha más a la derecha de lit está en N (invariante)
    // t = p: desde N, llega hasta N + p = new_n ✓ (t = p ≤ p_a)
    long long t = p;
    N = new_n;
    
    // Después del spread, están encendidas: union [s, s+t] para s in lit, ∩ [1,N]
    auto ivs = make_intervals(lit, t, N);
    
    // Queremos retornar subconjunto ≤ 150 de posiciones encendidas que incluya N
    // Usamos canónico desde N, filtrando solo las que están en ivs
    auto cand = canonical(N);
    
    vector<long long> result;
    for (long long pos : cand) {
        if (in_intervals(ivs, pos)) {
            result.push_back(pos);
        }
    }
    // Asegurar N está
    if (result.empty() || result.back() != N) {
        result.push_back(N);
        sort(result.begin(), result.end());
    }
    
    lit = result;
    return {t, lit};
}

pair<long long, vector<long long>> leave(long long p) {
    long long new_n = N - p;
    
    // Filtrar sobrevivientes (posición ≤ new_n)
    vector<long long> surviving;
    for (long long pos : lit) {
        if (pos <= new_n) surviving.push_back(pos);
    }
    
    // Necesitamos encender new_n. Antorcha más cercana a la izquierda de new_n en surviving:
    long long t = 0;
    if (!surviving.empty()) {
        long long rightmost_surv = surviving.back();
        t = new_n - rightmost_surv; // mínimo t para llegar a new_n
    } else {
        // Sin sobrevivientes: necesitamos t = 0? No puede pasar si 1 siempre está en lit
        // y new_n >= 1
        t = 0;
        surviving = {1};
    }
    
    // Verificar t ≤ p_a
    // Si t > p, hay un problema con nuestra estructura. 
    // Con canonical, la brecha máxima entre consecutivas es potencia de 2.
    // new_n está a distancia p de N. La antorcha en N desaparece.
    // La siguiente es N - 1 (si existe en lit). Si N-1 > new_n, también desaparece...
    // Necesitamos que haya una antorcha en [new_n - p, new_n] = [N - 2p, new_n].
    // Canonical incluye N-1, N-3, N-7, ... La primera que sea ≤ new_n = N-p:
    // N - (2^k - 1) ≤ N - p  →  2^k - 1 ≥ p  →  k ≥ log2(p+1)
    // Esa antorcha está en N - (2^k - 1) donde 2^k - 1 ≥ p,
    // así que t = new_n - (N - (2^k - 1)) = (N-p) - N + 2^k - 1 = 2^k - 1 - p
    // Si 2^k es la potencia mínima ≥ p+1, entonces 2^k ≤ 2p (si p ≥ 1),
    // así t = 2^k - 1 - p ≤ 2p - 1 - p = p - 1 < p ✓ 
    // → t ≤ p siempre! ✓
    
    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);
        }
    }
    if (result.empty() || result.back() != N) {
        result.push_back(N);
        sort(result.begin(), result.end());
    }
    
    lit = result;
    return {t, lit};
}
```

## Explicación de la solución

### Invariante clave
Mantenemos antorchas en posiciones `n, n-1, n-3, n-7, n-15, ...` (es decir, `n - (2^k - 1)` para k=0,1,2,...), que son O(log N) ≤ 60 posiciones → siempre ≤ 150 ✓

### Por qué t ≤ p siempre:

**join(p):** La antorcha en `n` alcanza `n+p` con exactamente `t = p` ✓

**leave(p):** El nuevo extremo es `n-p`. La antorcha sobreviviente más cercana está en `n - (2^k - 1)` donde `2^k` es la potencia mínima ≥ p+1. Entonces:
```
t = (n-p) - (n - (2^k-1)) = 2^k - 1 - p ≤ 2p - 1 - p = p-1 < p ✓

Compilation message (stderr)

light.cpp:184:1: error: stray '`' in program
  184 | ```
      | ^
light.cpp:184:2: error: stray '`' in program
  184 | ```
      |  ^
light.cpp:184:3: error: stray '`' in program
  184 | ```
      |   ^
light.cpp:186:1: error: stray '##' in program
  186 | ## Explicación de la solución
      | ^~
light.cpp:188:1: error: stray '##' in program
  188 | ### Invariante clave
      | ^~
light.cpp:188:3: error: stray '#' in program
  188 | ### Invariante clave
      |   ^
light.cpp:189:36: error: stray '`' in program
  189 | Mantenemos antorchas en posiciones `n, n-1, n-3, n-7, n-15, ...` (es decir, `n - (2^k - 1)` para k=0,1,2,...), que son O(log N) ≤ 60 posiciones → siempre ≤ 150 ✓
      |                                    ^
light.cpp:189:64: error: stray '`' in program
  189 | Mantenemos antorchas en posiciones `n, n-1, n-3, n-7, n-15, ...` (es decir, `n - (2^k - 1)` para k=0,1,2,...), que son O(log N) ≤ 60 posiciones → siempre ≤ 150 ✓
      |                                                                ^
light.cpp:189:77: error: stray '`' in program
  189 | Mantenemos antorchas en posiciones `n, n-1, n-3, n-7, n-15, ...` (es decir, `n - (2^k - 1)` para k=0,1,2,...), que son O(log N) ≤ 60 posiciones → siempre ≤ 150 ✓
      |                                                                             ^
light.cpp:189:91: error: stray '`' in program
  189 | Mantenemos antorchas en posiciones `n, n-1, n-3, n-7, n-15, ...` (es decir, `n - (2^k - 1)` para k=0,1,2,...), que son O(log N) ≤ 60 posiciones → siempre ≤ 150 ✓
      |                                                                                           ^
light.cpp:189:129: error: extended character ≤ is not valid in an identifier
  189 | Mantenemos antorchas en posiciones `n, n-1, n-3, n-7, n-15, ...` (es decir, `n - (2^k - 1)` para k=0,1,2,...), que son O(log N) ≤ 60 posiciones → siempre ≤ 150 ✓
      |                                                                                                                                 ^
light.cpp:189:145: error: extended character → is not valid in an identifier
  189 | Mantenemos antorchas en posiciones `n, n-1, n-3, n-7, n-15, ...` (es decir, `n - (2^k - 1)` para k=0,1,2,...), que son O(log N) ≤ 60 posiciones → siempre ≤ 150 ✓
      |                                                                                                                                                 ^
light.cpp:189:155: error: extended character ≤ is not valid in an identifier
  189 | Mantenemos antorchas en posiciones `n, n-1, n-3, n-7, n-15, ...` (es decir, `n - (2^k - 1)` para k=0,1,2,...), que son O(log N) ≤ 60 posiciones → siempre ≤ 150 ✓
      |                                                                                                                                                           ^
light.cpp:189:161: error: extended character ✓ is not valid in an identifier
  189 | Mantenemos antorchas en posiciones `n, n-1, n-3, n-7, n-15, ...` (es decir, `n - (2^k - 1)` para k=0,1,2,...), que son O(log N) ≤ 60 posiciones → siempre ≤ 150 ✓
      |                                                                                                                                                                 ^
light.cpp:191:1: error: stray '##' in program
  191 | ### Por qué t ≤ p siempre:
      | ^~
light.cpp:191:3: error: stray '#' in program
  191 | ### Por qué t ≤ p siempre:
      |   ^
light.cpp:191:15: error: extended character ≤ is not valid in an identifier
  191 | ### Por qué t ≤ p siempre:
      |               ^
light.cpp:193:29: error: stray '`' in program
  193 | **join(p):** La antorcha en `n` alcanza `n+p` con exactamente `t = p` ✓
      |                             ^
light.cpp:193:31: error: stray '`' in program
  193 | **join(p):** La antorcha en `n` alcanza `n+p` con exactamente `t = p` ✓
      |                               ^
light.cpp:193:41: error: stray '`' in program
  193 | **join(p):** La antorcha en `n` alcanza `n+p` con exactamente `t = p` ✓
      |                                         ^
light.cpp:193:45: error: stray '`' in program
  193 | **join(p):** La antorcha en `n` alcanza `n+p` con exactamente `t = p` ✓
      |                                             ^
light.cpp:193:63: error: stray '`' in program
  193 | **join(p):** La antorcha en `n` alcanza `n+p` con exactamente `t = p` ✓
      |                                                               ^
light.cpp:193:69: error: stray '`' in program
  193 | **join(p):** La antorcha en `n` alcanza `n+p` con exactamente `t = p` ✓
      |                                                                     ^
light.cpp:193:71: error: extended character ✓ is not valid in an identifier
  193 | **join(p):** La antorcha en `n` alcanza `n+p` con exactamente `t = p` ✓
      |                                                                       ^
light.cpp:195:35: error: stray '`' in program
  195 | **leave(p):** El nuevo extremo es `n-p`. La antorcha sobreviviente más cercana está en `n - (2^k - 1)` donde `2^k` es la potencia mínima ≥ p+1. Entonces:
      |                                   ^
light.cpp:195:39: error: stray '`' in program
  195 | **leave(p):** El nuevo extremo es `n-p`. La antorcha sobreviviente más cercana está en `n - (2^k - 1)` donde `2^k` es la potencia mínima ≥ p+1. Entonces:
      |                                       ^
light.cpp:195:88: error: stray '`' in program
  195 | **leave(p):** El nuevo extremo es `n-p`. La antorcha sobreviviente más cercana está en `n - (2^k - 1)` donde `2^k` es la potencia mínima ≥ p+1. Entonces:
      |                                                                                        ^
light.cpp:195:102: error: stray '`' in program
  195 | **leave(p):** El nuevo extremo es `n-p`. La antorcha sobreviviente más cercana está en `n - (2^k - 1)` donde `2^k` es la potencia mínima ≥ p+1. Entonces:
      |                                                                                                      ^
light.cpp:195:110: error: stray '`' in program
  195 | **leave(p):** El nuevo extremo es `n-p`. La antorcha sobreviviente más cercana está en `n - (2^k - 1)` donde `2^k` es la potencia mínima ≥ p+1. Entonces:
      |                                                                                                              ^
light.cpp:195:114: error: stray '`' in program
  195 | **leave(p):** El nuevo extremo es `n-p`. La antorcha sobreviviente más cercana está en `n - (2^k - 1)` donde `2^k` es la potencia mínima ≥ p+1. Entonces:
      |                                                                                                                  ^
light.cpp:195:138: error: extended character ≥ is not valid in an identifier
  195 | **leave(p):** El nuevo extremo es `n-p`. La antorcha sobreviviente más cercana está en `n - (2^k - 1)` donde `2^k` es la potencia mínima ≥ p+1. Entonces:
      |                                                                                                                                          ^
light.cpp:196:1: error: stray '`' in program
  196 | ```
      | ^
light.cpp:196:2: error: stray '`' in program
  196 | ```
      |  ^
light.cpp:196:3: error: stray '`' in program
  196 | ```
      |   ^
light.cpp:197:41: error: extended character ≤ is not valid in an identifier
  197 | t = (n-p) - (n - (2^k-1)) = 2^k - 1 - p ≤ 2p - 1 - p = p-1 < p ✓
      |                                         ^
light.cpp:197:64: error: extended character ✓ is not valid in an identifier
  197 | t = (n-p) - (n - (2^k-1)) = 2^k - 1 - p ≤ 2p - 1 - p = p-1 < p ✓
      |                                                                ^
light.cpp:186:4: error: 'Explicaci\U000000f3n' does not name a type
  186 | ## Explicación de la solución
      |    ^~~~~~~~~~~