Задача №114969. Блочная сортировка
Васе недавно подарили перестановку из \(n\) чисел. Он очень любит играть с перестановками. Играет он так: сначала перемешивает её, затем разбивает её на \(k\) непустых блоков так, что каждый элемент перестановки принадлежит ровно одному блоку. После этого Вася сортирует каждый из \(k\) блоков перестановки по отдельности. Вася хочет, чтобы после этого вся перестановка была отсортирована.
В этот раз ему подарили слишком большую перестановку, поэтому после того, как Вася перемешал перестановку, он понял, что не знает какие именно выбрать блоки. Помогите ему разбить перестановку ровно на \(k\) блоков или скажите, что это невозможно сделать.
Более формально, перестановку требуется разбить на ровно на \(k\) непустых подотрезков (каждый элемент должен принадлежать ровно одному подотрезку) так, чтобы если отсортировать элементы каждого из этих подотрезков по-отдельности, то в итоге получится отсортированный массив.
Перестановкой является массив, состоящий из \(n\) различных целых чисел от \(1\) до \(n\) в произвольном порядке. Например, \([2,3,1,5,4]\) — перестановка, но \([1,2,2]\) не перестановка (\(2\) встречается в массиве дважды) и \([1,3,4]\) тоже не перестановка (\(n=3\), но в массиве встречается \(4\)).
Последовательность \(a\) является непустым подотрезком \(b\), если \(a\) содержит хотя бы один элемент и \(a\) может быть получена из \(b\) удалением нескольких (возможно, ни одного) элементов из начала и нескольких (возможно, ни одного) элементов из конца \(b\).
Первая строка содержит два целых числа \(n\) и \(k\) (\(1 \le k \le n \le 2 \cdot 10^5\)) — размер перестановки и число блоков, на которые её надо разбить.
Вторая строка содержит \(n\) различных целых чисел \(p_1, p_2, \ldots, p_n\) (\(1 \le p_i \le n\)) — значения чисел в перестановке.
В единственной строке выведите \(k\) чисел — длины блоков, на которые надо разбить перестановку (сумма длин блоков должна равняться \(n\)). Если решений несколько, разрешается вывести любое из них. Если так разбить массив на \(k\) блоков невозможно, выведите единственное число \(-1\).
В первом наборе входных данных можно разбить перестановку на \(2\) блока так: \([2,3,1]\) и \([5,4]\). Отдельно их отсортировав получим: \([1,2,3]\) и \([4,5]\). Если соединить их, то получится отсортированная последовательность.
Во втором наборе входных данных нужно разбить перестановку на \(1\) блок, и это можно сделать единственным способом: \([2,1,4,3,5]\). Отсортируем единственный блок и получим отсортированную последовательность.
В третьем наборе входных данных можно показать, что разбиения на блоки не существует.
Тесты к этой задаче состоят из 4 групп, не считая тесты из условия. Баллы за каждую группу ставятся только при прохождении всех тестов группы и всех тестов некоторых из предыдущих групп.
| Доп. ограничения | ||||
| Группа | Баллы | \(n\) | Необх. группы | Комментарий |
| 0 | 0 | – | – | Тесты из условия. |
| 1 | 21 | \(n \le 100\) | 0 | |
| 2 | 22 | \(n \le 1000\) | 0, 1 | |
| 3 | 18 | \(n \le 10\,000\) | 0 — 2 | |
| 4 | 39 | \(n \le 200\,000\) | 0 — 3 |
5 2 2 3 1 5 4
3 2
5 1 2 1 4 3 5
5
5 3 4 3 2 1 5
-1