Codeforces Global Round 26 |
---|
Закончено |
Секрет первого фокуса Оскара раскрыт! Поскольку он все еще хочет произвести впечатление на Луру, ему пришла в голову новая идея: он по-прежнему хочет отсортировать перестановку $$$p_1, p_2, \ldots, p_n$$$ из $$$[1, 2, \ldots, n]$$$.
На этот раз он выбирает целое число $$$k$$$. Он хочет отсортировать перестановку в неубывающем порядке, используя следующую операцию несколько раз:
Чтобы произвести впечатление, Оскар хочет выбрать максимальное значение $$$k$$$, при котором он сможет отсортировать свою перестановку. Пожалуйста, помогите ему найти максимальное значение $$$k$$$, а также последовательность операций, которые отсортируют перестановку. Вам не нужно минимизировать количество операций, но разрешается использовать не более $$$5n^2$$$ операций.
Можно доказать, что для максимального $$$k$$$, при котором перестановку можно отсортировать за любое количество операций, ее также можно отсортировать за не более чем $$$5n^2$$$ операций.
Каждый тест состоит из нескольких наборов входных данных. Первая строка содержит одно целое число $$$t$$$ ($$$1 \leq t \leq 10^3$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.
Первая строка каждого набора входных данных содержит одно целое число $$$n$$$ ($$$5 \leq n \leq 10^3$$$) — длина перестановки.
Вторая строка каждого набора входных данных содержит перестановку $$$p_1, p_2, \ldots, p_n$$$ из $$$[1, 2, \ldots, n]$$$.
Сумма $$$n$$$ по всем наборам входных данных не превосходит $$$2 \cdot 10^3$$$.
Для каждого набора входных данных сначала выведите в отдельной строке выбранное значение $$$k$$$ ($$$1 \leq k \leq n$$$).
Затем выведите одно целое число $$$m$$$ — количество использованных операций ($$$0 \leq m \leq 5n^2$$$).
Затем в каждой из следующих $$$m$$$ строк выведите операции, обозначенные двумя целыми числами $$$i$$$ и $$$j$$$ ($$$1 \leq i, j \leq n - k + 1$$$), представляющие собой операции удаления подмассива, начинающегося с индекса $$$i$$$, и его вставки обратно в $$$p$$$, начиная с индекса $$$j$$$.
355 1 2 3 452 3 5 4 161 2 3 4 5 6
4 1 2 1 3 2 1 3 2 1 6 0
В первом наборе входных данных достаточно переместить последние четыре числа в начало.
Во втором наборе входных данных можно показать, что мы не можем отсортировать перестановку при $$$k = 4$$$ или $$$k = 5$$$. При $$$k = 3$$$ мы можем переместить первые три числа в конец, а затем средние три —- в начало, чтобы отсортировать перестановку.
В третьем наборе входных данных перестановка уже отсортирована. Мы можем выбрать $$$k = 6$$$ и не использовать никаких операций.
Название |
---|