Ordenação Estável
Alguns algoritmos de ordenação preservam a ordem relativa dos itens que possuem chaves de ordenação iguais. Nesse cenário, dizemos que o algoritmo realiza uma ordenação estável.
Imagine que escrevemos os números do array juntamente com seus índices iniciais, para depois de ordenar vermos onde cada elemento foi colocado.
Array inicial | (10, 0) | (12, 1) | (10, 2) | (7, 3) | (-3, 4) | (-3, 5) | (7, 6) |
Ordenação estável | (-3, 4) | (-3, 5) | (7, 3) | (7, 6) | (10, 0) | (10, 2) | (12, 1) |
Ordenação instável | (-3, 5) | (-3, 4) | (7, 3) | (7, 6) | (10, 2) | (10, 0) | (12, 1) |
Quando aplicamos uma ordenação estável, o algoritmo mantém a ordem original sempre que os elementos são iguais. No caso de uma ordenação instável, essa ordem pode ser alterada.
Desafio
Dado um array inicial de
n inteiros e n índices , deve-se formar um novo array selecionando os elementos na ordem indicada por esses índices. Ou seja, o primeiro elemento do novo array será , o segundo será e assim por diante.O objetivo é verificar se o array obtido corresponde à versão do array inicial ordenada de forma estável.
Entrada
A primeira linha da entrada contém um único inteiro
n (1 ≤ n ≤ ).A linha seguinte contém
n inteiros separados por espaço ( ≤ ≤ ).A próxima linha contém
n inteiros separados por espaço (0 ≤ < n).Saída
O programa deve imprimir
Yes se a ordem dos índices corresponder ao resultado de uma ordenação estável de , ou No caso contrário.Exemplos
Entrada | Saída |
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