Seguridad


Submit solution

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

Author:
Problem type
Allowed languages
Ada, Assembly, Awk, BrainF***, C, C#, C++, Dart, Go, Java, JS, Kotlin, Lua, Pascal, Perl, Prolog, Python, Scala, Swift, VB

En el Instituto de Seguridad de la Información de IslaGrande (ISII) los científicos están trabajando en nuevas formas de proteger la información almacenada y transmitida.

Recientemente, el Instituto desarrolló un método innovador de seguridad de transmisión de una secuencia numérica, llamado “Seguridad estática”. La idea es simple: se expone una secuencia de números al proceso de encriptación y el resultado es dos nuevas series de números: el cifrado y la llave. El proceso de encriptación se mantiene en secreto, pero los miembros del Instituto desean contratar a un programador para que implemente un decodificador. El decodificador necesita recibir la secuencia de números encriptados y la llave como entrada y debe retornar la secuencia de números original.

Como usted es uno de los mejores programadores de IslaGrande fue invitado a participar en el desarrollo del decodificador.

En el ISII le darán todos los detalles del decodificador. Este toma la secuencia encriptada de longitud N y un parámetro M, el cual especifica el tamaño de los bloques de la secuencia procesados. Un bloque de la secuencia se representa por M elementos consecutivos de la secuencia. Para restaurar la secuencia original de longitud K se necesita una llave de K enteros k_i.

El decodificador recupera los elementos de la secuencia uno a uno. Para restaurar el i-ésimo elemento de la secuencia original se necesita calcular el k_i-ésimo orden estático para cada bloque: el número que estará en la k_i-ésima posición después de ordenar todos los elementos del bloque. El elemento de la posición i de la secuencia original es igual al mayor valor del orden estático calculado. Conociendo el esquema de decodificación, escriba un programa que pueda ser usado para desencriptar la secuencia encriptada dada.

Entrada

La primera línea de la entrada contienen tres enteros N, M, K (1 \leq N \leq 250\,000; 1 \leq K \leq M \leq N) — el número de elementos de la secuencia encriptada, el parámetro del decodificador y el número de elementos de la secuencia original, respectivamente.

La segunda línea contiene N enteros diferentes a_i (1 \leq a_i \leq 250\,000) — los elementos de la secuencia encriptada. La última línea contiene K enteros diferentes k_i (1 \leq k_i \leq M) – los elementos de la llave de desencriptado.

Los números en las líneas están separados por un espacio.

Salida

La salida debe contener K enteros representando la secuencia desencriptada.

Ejemplos

Entrada 1
5 2 2
1 5 3 2 6
1 2
Salida 1
3 6
Explicación 1

Consideremos todas las secuencias de bloques: (1, 5); (5, 3); (3, 2) y (2, 6). El primer elemento de la secuencia original es igual al mayor de los mínimos de los bloques, es decir 3. El segundo elemento de la secuencia original es igual al mayor de los máximos de los bloques, es decir 6.

Entrada 2
4 3 2
5 7 3 4
3 2
Salida 2
7 5
Explicación 2

Aquí tenemos dos bloques: (5, 7, 3); (7, 3, 4). El primer elemento es igual al mayor elemento de los máximos de los bloques, es decir 7. El segundo es igual al mayor de los medianas (el segundo elemento por valor), es decir 5.


Comments


  • 1
    Osvaldo23  commented on June 6, 2022, 8:29 a.m.

    Esto es veneno estoy seguro q pocos se meten aquí,esto es un problema con colas y lo q hay q hacer es trabajar con los mínimos en cada uno de los bloques meterlos en una lista ,remover esos valores de los bloques y sustraer de esa lista el max meterlo en una lista y repetir el proceso,entonces todo te quedara ordenado segun las llaves


  • 1
    Pimienta  commented on Aug. 9, 2021, 9:28 p.m.

    Le raspé 12 puntos trabajando con colas y esas cosas. Sería muy cool si alguien pudiera decirme de q va este ejercicio...


  • 1
    Primervirgen  commented on Dec. 30, 2019, 4:37 p.m.

    Alguien me puede dar una idea d como resolver este problema???