Stabile Sortierung
Einige Sortieralgorithmen behalten die relative Reihenfolge von Elementen bei, wenn diese den gleichen Sortierschlüssel haben. In diesen Fällen sagen wir, dass der Algorithmus eine stabile Sortierung ausführt.
Stellen wir uns vor, wir notieren die Zahlen im Array zusammen mit ihren ursprünglichen Indizes. Nach dem Sortieren können wir dann erkennen, wie sich die Position jedes Elements verändert:
Ursprüngliches Array | (10, 0) | (12, 1) | (10, 2) | (7, 3) | (-3, 4) | (-3, 5) | (7, 6) |
Stabile Sortierung | (-3, 4) | (-3, 5) | (7, 3) | (7, 6) | (10, 0) | (10, 2) | (12, 1) |
Instabile Sortierung | (-3, 5) | (-3, 4) | (7, 3) | (7, 6) | (10, 2) | (10, 0) | (12, 1) |
Bei einer stabilen Sortierung behält ein Algorithmus die ursprüngliche Reihenfolge gleichwertiger Elemente bei. Bei einer instabilen Sortierung kann diese Reihenfolge verändert werden.
Aufgabe
Gegeben ist ein anfängliches Array von
n ganzen Zahlen sowie n Indizes . Aus diesen soll ein neues Array erzeugt werden, indem die Elemente in genau der Reihenfolge angeordnet werden, die durch die Indizes bestimmt ist. Das heißt, das erste Element des neuen Arrays ist , das zweite ist und so weiter.Nun soll überprüft werden, ob das auf diese Weise erhaltene Array mit der stabil sortierten Version des ursprünglichen Arrays übereinstimmt.
Eingabe
Die erste Zeile der Eingabe enthält eine einzelne ganze Zahl
n (1 ≤ n ≤ ).Die nächste Zeile enthält
n durch Leerzeichen getrennte ganze Zahlen ( ≤ ≤ ).Die nachfolgende Zeile enthält
n durch Leerzeichen getrennte ganze Zahlen (0 ≤ < n).Ausgabe
Das Programm soll
Yes ausgeben, wenn die Reihenfolge der Indizes dem Ergebnis einer stabilen Sortierung von entspricht, andernfalls No.Beispiele
Eingabe | Ausgabe |
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