Ordinamento stabile
Alcuni algoritmi di ordinamento mantengono l’ordine relativo degli elementi che hanno la stessa chiave di ordinamento. In questi casi, diciamo che l’algoritmo esegue un ordinamento stabile.
Immaginiamo di scrivere i numeri nell’array insieme ai loro indici iniziali, così da poter vedere come ogni elemento si sposta dopo l’ordinamento.
Initial array | (10, 0) | (12, 1) | (10, 2) | (7, 3) | (-3, 4) | (-3, 5) | (7, 6) |
Stable sorting | (-3, 4) | (-3, 5) | (7, 3) | (7, 6) | (10, 0) | (10, 2) | (12, 1) |
Unstable sorting | (-3, 5) | (-3, 4) | (7, 3) | (7, 6) | (10, 2) | (10, 0) | (12, 1) |
Quando si esegue un ordinamento stabile, un algoritmo mantiene l’ordine iniziale se gli elementi sono uguali. Al contrario, in un ordinamento instabile, tale ordine può cambiare.
Challenge
Dato un array iniziale di
n interi e n indici , occorre ottenere un nuovo array prendendo gli elementi nell’ordine indicato dagli indici forniti. Il primo elemento del nuovo array deve essere , il secondo deve essere , e così via.Bisogna verificare se l’array ottenuto corrisponde alla versione stabilmente ordinata dell’array iniziale.
Input
La prima riga dell’input contiene un unico intero
n (1 ≤ n ≤ ).La riga successiva contiene
n interi separati da spazio ( ≤ ≤ ).La riga seguente contiene
n interi separati da spazio (0 ≤ < n).Output
Il programma deve stampare
Yes se l’ordine degli indici corrisponde al risultato di un ordinamento stabile di , altrimenti deve stampare No.Esempi
Input | Output |
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