Tri stable
Certains algorithmes de tri conservent l’ordre relatif des éléments qui possèdent la même clé de tri. Dans ce cas, on dit que l’algorithme effectue un tri stable.
Imaginons que nous inscrivions les nombres du tableau ainsi que leurs indices initiaux pour observer comment chaque élément est déplacé après le tri.
Tableau initial | (10, 0) | (12, 1) | (10, 2) | (7, 3) | (-3, 4) | (-3, 5) | (7, 6) |
Tri stable | (-3, 4) | (-3, 5) | (7, 3) | (7, 6) | (10, 0) | (10, 2) | (12, 1) |
Tri instable | (-3, 5) | (-3, 4) | (7, 3) | (7, 6) | (10, 2) | (10, 0) | (12, 1) |
Lors d’un tri stable, l’algorithme conserve l’ordre initial si deux éléments sont égaux. Cependant, dans le cas d’un tri instable, cet ordre peut changer.
Défi
Étant donné un tableau initial de
n entiers , ainsi que n indices , vous devez construire un nouveau tableau en prenant les éléments dans l’ordre indiqué par ces indices. Le premier élément du nouveau tableau sera , le deuxième sera , etc.Vous devez vérifier si le tableau obtenu correspond au résultat d’un tri stable sur .
Entrée
La première ligne de l’entrée contient un seul entier
n (1 ≤ n ≤ ).La ligne suivante contient
n entiers séparés par des espaces ( ≤ ≤ ).La troisième ligne contient
n entiers séparés par des espaces (0 ≤ < n).Sortie
Le programme doit afficher « Yes » si l’ordre des indices correspondrait au résultat d’un tri stable sur , et « No » sinon.
Exemples
Entrée | Sortie |
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