teddy online judge

908. Bandera nacional holandesa

Limite de tiempo : 1 seg.   Total runs : 142  Aceptados : 14

El algoritmo de ordenación quicksort procede de manera recursiva: selecciona un elemento (el pivote), y reordena la matriz para que todos los elementos menores o iguales al pivote aparezcan primero, seguido de todos los elementos mayores que el pivote. Despues, los dos subconjuntos se ordenan de forma recursiva.

Esto se conoce como el problema de partición de la bandera nacional holandesa, debido a que la bandera holandesa nacional consiste de tres bandas horizontales cada una de un color diferente.

Escribe un programa que tome una matriz A, un índice i, y reordene los elementos de tal manera que todos los elementos menores que A[i] (el pivote) aparezcan primero, seguido de los elementos iguales al pivote, y finalmente de los elementos mayores que el pivote.

Entrada

Un numero de casos c, seguido de c lineas. Cada linea comienza con el numero de elementos en el arreglo i, seguido del indice del pivote en el arreglo, seguido del arreglo en si: n₀, n₁, n₂ ... n_i-1.

Salida

Una linea por cada caso de entrada, donde cada linea contiene el arreglo ordenado

Restricciones

0 ≤ n_i ≤ 2,147,483,648

0 < i ≤ 5000

Entrada de ejemplo

3
10 4 1 2 3 4 5 6 7 8 9 10
10 5 10 9 8 7 6 5 4 3 2 1
10 8 1 10 3 9 2 8 4 7 5 6

Salida de ejemplo

1 2 3 4 5 6 7 8 9 10
4 3 2 1 5 10 9 8 7 6
1 3 2 4 5 10 9 8 7 6