Decodificador

Points: 100 (partial)

Time limit: 1.0s

Memory limit: 500M

Authors:

frankr, eliogovea

Problem type

Allowed languages

Ada, BrainF***, C, C#, C++, Dart, Go, Java, JS, Kotlin, Lua, Pascal, Prolog, Python, Swift, VB

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

Se pide que dado $B$ ~B~ encontrar $A$ ~A~.

Nota: Una permutación con $n$ ~n~ elementos contiene todos los numeros desde $1$ ~1~ hasta $n$ ~n~ exactamente una vez.

Entrada

Una línea con un número $n$ ~n~.

$n$ ~n~ líneas cada una con un numero $b_i$ ~b_i~ que representan la descripción de la codificación de una permutación.

Salida

$n$ ~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, 7:43 p.m.

emmm? alguien me explica?

6

aniervs commented on Feb. 8, 2020, 9:47 p.m. ← edited →

Mi solución: Vamos a ir hallando las posiciones de los valores en orden decreciente, primero donde está $n$ ~n~, luego $n-1$ ~n-1~, y así hasta llegar a $1$ ~1~. Digamos que el $0$ ~0~ más a la derecha está en la posición $p$ ~p~, entonces $a_p = n$ ~a_p = n~. Ahora eliminamos esa posición del arreglo $b[\ ]$ ~b[\ ]~. Ahora observemos que $n$ ~n~ aportaba $+1$ ~+1~ a $b_i$ ~b_i~ para los $i > p$ ~i > p~, así que al eliminarlo debemos restarle $1$ ~1~ a todos los $b_i$ ~b_i~ para $i > p$ ~i > p~. Luego el nuevo $0$ ~0~ más a la derecha es la posición de $n-1$ ~n-1~, y hacemos lo mismo, lo eliminamos y le restamos $1$ ~1~ a todos $b_i$ ~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)$ ~O(\log n)~, por lo que esta solución tiene complejidad $O(n\log n)$ ~O(n\log n)~.