Decodificador

View as PDF

Submit solution

Points: 100 (partial)
Time limit: 1.0s
Memory limit: 500M

Authors:
Problem type
Allowed languages
C, C++, Java, Lua, Pascal, Python

Cada permutación \(A = \{a_1, a_2, ..., a_n\}\) puede ser codificada como una secuencia \(B = \{b_1, b_2, ..., b_n\}\) en la que \(b_i\) es igual a la cantidad de \(a_j\) tal que \(j < i\) y \(a_i < a_j\).

Se pide que dado \(B\) encontrar \(A\).

Nota: Una permutación con \(n\) elementos contiene todos los numeros desde \(1\) hasta \(n\) exactamente una vez.

Entrada

Una línea con un número \(n\).

\(n\) líneas cada una con un numero \(b_i\) que representan la descripción de la codificación de una permutación.

Salida

\(n\) líneas con la descripción de la permutación.

Ejemplo de entrada

2
0
0

Ejemplo de salida

1
2

Comments


  • 0
    Alejandro777  commented on Feb. 8, 2020, 2:43 p.m.

    emmm? alguien me explica?


    • 0
      aniervs  commented on Feb. 8, 2020, 4:47 p.m. edited

      Mi solución: Vamos a ir hallando las posiciones de los valores en orden decreciente, primero donde está \(n\), luego \(n-1\), y así hasta llegar a \(1\). Digamos que el \(0\) más a la derecha está en la posición \(p\), entonces \(a_p = n\). Ahora eliminamos esa posición del arreglo \(b[\ ]\). Ahora observemos que \(n\) aportaba \(+1\) a \(b_i\) para los \(i > p\), así que al eliminarlo debemos restarle \(1\) a todos los \(b_i\) para \(i > p\). Luego el nuevo \(0\) más a la derecha es la posición de \(n-1\), y hacemos lo mismo, lo eliminamos y le restamos \(1\) a todos \(b_i\) a su derecha, y así sucesivamente. Entonces para hacer estas operaciones eficientemente podemos usar un Segment Tree con Lazy Update, con el cual podemos hacer cada operación en \(O(\log n)\), por lo que esta solución tiene complejidad \(O(n\log n)\).