Ordenamiento estable
Algunos algoritmos de ordenamiento mantienen el orden relativo de aquellos elementos que tienen la misma clave de ordenación. En esos casos, decimos que el algoritmo realiza un ordenamiento estable.
Imagina que escribimos los números del arreglo junto con sus índices iniciales para que, después de ordenar, podamos ver a dónde se desplazó cada elemento.
Arreglo inicial | (10, 0) | (12, 1) | (10, 2) | (7, 3) | (-3, 4) | (-3, 5) | (7, 6) |
Ordenamiento estable | (-3, 4) | (-3, 5) | (7, 3) | (7, 6) | (10, 0) | (10, 2) | (12, 1) |
Ordenamiento inestable | (-3, 5) | (-3, 4) | (7, 3) | (7, 6) | (10, 2) | (10, 0) | (12, 1) |
Cuando se lleva a cabo un ordenamiento estable, el algoritmo conserva el orden inicial si los elementos son iguales. Sin embargo, con un ordenamiento inestable, ese orden puede cambiar.
Desafío
Dado un arreglo inicial de
n enteros , y n índices , debes formar un nuevo arreglo tomando los elementos en el orden indicado por dichos índices. El primer elemento del nuevo arreglo será , el segundo será , etc.Se te pide comprobar si el arreglo obtenido correspondería al resultado de aplicar un ordenamiento estable al arreglo inicial.
Entrada
La primera línea de la entrada contiene un único entero
n (1 ≤ n ≤ ).La siguiente línea contiene
n enteros separados por espacios: ( ≤ ≤ ).La siguiente línea contiene
n enteros separados por espacios: (0 ≤ < n).Salida
El programa debe imprimir
Yes si el orden de los índices corresponde a un ordenamiento estable de , o No en caso contrario.Ejemplos
Entrada | Salida |
8
10 12 10 7 -3 4 -3 5
4 6 5 7 3 0 2 1 | Yes |
8
10 12 10 7 -3 4 -3 5
6 4 5 7 3 2 0 1 | No |
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB