Стабильная сортировка
Некоторые алгоритмы сортировки сохраняют относительный порядок элементов, у которых совпадают ключи для сортировки. В таких случаях мы говорим, что алгоритм выполняет стабильную сортировку.
Представьте, что мы записали числа в массиве вместе с их начальными индексами, чтобы после сортировки можно было проследить, как каждый элемент сместился.
Исходный массив | (10, 0) | (12, 1) | (10, 2) | (7, 3) | (-3, 4) | (-3, 5) | (7, 6) |
Стабильная сортировка | (-3, 4) | (-3, 5) | (7, 3) | (7, 6) | (10, 0) | (10, 2) | (12, 1) |
Нестабильная сортировка | (-3, 5) | (-3, 4) | (7, 3) | (7, 6) | (10, 2) | (10, 0) | (12, 1) |
При стабильной сортировке алгоритм сохраняет исходный порядок для равных по значению элементов. Однако при нестабильной сортировке этот порядок может меняться.
Задача
Пусть дан исходный массив из
n целых чисел и n индексов . Необходимо сформировать новый массив, следуя порядку, заданному этими индексами: первый элемент нового массива будет , второй — и так далее.Нужно проверить, является ли полученный массив результатом стабильной сортировки исходного массива.
Входные данные
В первой строке входного файла содержится одно целое число
n (1 ≤ n ≤ ).Во второй строке записаны
n целых чисел ( ≤ ≤ ).В третьей строке содержатся
n целых чисел (0 ≤ < n).Выходные данные
Программа должна вывести
Yes, если порядок индексов действительно соответствует результату стабильной сортировки массива , и No — в противном случае.Примеры
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