Cambios en Arreglo

View as PDF

Submit solution

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

Author:
Problem types

Alex tiene un arreglo \(a\) de \(N\) enteros y un entero \(K\). Él puede cambiar cualquier par de elementos adyacentes del arreglo a lo más \(K\) veces. Alex quiere saber cuál es el mayor arreglo en orden lexicográfico que puede obtener. Ayúdalo.

Entrada

La primera línea contiene los enteros \(N\) y \(K \; (1 \leq N \leq 10^5; 0 \leq K \leq 5 \cdot 10^9)\). La segunda línea contiene \(N\) enteros \(a_i \; (0 \leq a_i \leq 10^9)\) separados entre sí por un espacio, estos son los elementos del arreglo.

Salida

En una única línea imprima los \(N\) elementos del mayor arreglo en orden lexicográfico que se puede obtener.

Ejemplos

Entrada 1
4 2
1 3 2 4
Salida 1
3 2 1 4
Entrada 2
4 3
1 3 2 3
Salida 2
3 3 1 2
Entrada 3
6 6
1 2 2 3 2 3
Salida 3
3 2 2 2 1 3
Entrada 4
6 7
1 2 2 3 2 3
Salida 4
3 3 1 2 2 2

Explicación de los ejemplos

En el primer ejemplo lo mejor es cambiar los pares de posiciones \((1, 2)\) y \((2, 3)\) en este orden.

En el segundo ejemplo lo mejor es cambiar los pares de posiciones \((1, 2)\), \((3, 4)\) y \((2, 3)\) en este orden.

Nota

Un arreglo \(a\) de tamaño \(n\) es lexicográficamente mayor que un arreglo \(b\) de tamaño \(n\) si existe un \(k < n\) tal que \(a_1 = b_1, a_2 = b_2, \ldots, a_k = b_k\) y \(a_{k + 1} > b_{k + 1}\).


Comments

There are no comments at the moment.