Codeforces Round 935 (Div. 3) |
---|
Закончено |
Антону стало скучно в походе, и он захотел что-нибудь порешать. Он спросил у Кирилла, нет ли у него какой-то новой задачи, и у Кирилла она естественно нашлась.
Дана перестановка $$$p$$$ размера $$$n$$$, а также число $$$x$$$, которое необходимо найти. Перестановкой длины $$$n$$$ является массив, состоящий из $$$n$$$ различных целых чисел от $$$1$$$ до $$$n$$$ в произвольном порядке. Например, $$$[2,3,1,5,4]$$$ — перестановка, но $$$[1,2,2]$$$ не перестановка ($$$2$$$ встречается в массиве дважды) и $$$[1,3,4]$$$ тоже не перестановка ($$$n=3$$$, но в массиве встречается $$$4$$$).
Вы решили, что вы крутой программист, поэтому будете использовать для поиска продвинутый алгоритм — бинарный поиск. Однако, вы забыли, что для бинарного поиска массив должен быть отсортирован.
Вы не отчаялись и решили все равно применить этот алгоритм, а чтобы получить правильный ответ, вы перед запуском алгоритма можете не более $$$2$$$ раз выполнить следующую операцию: выбрать индексы $$$i$$$, $$$j$$$ ($$$1\le i, j \le n$$$) и поменять местами элементы на позициях $$$i$$$ и $$$j$$$.
После этого выполняется бинарный поиск. В начале алгоритма объявляются две переменные $$$l = 1$$$ и $$$r = n + 1$$$. Далее выполняется цикл:
Цель — до алгоритма переставить числа в перестановке так, чтобы после выполнения алгоритма $$$p_l$$$ было равно $$$x$$$. Можно показать, что $$$2$$$ операции всегда достаточно.
Каждый тест состоит из нескольких наборов входных данных. В первой строке находится одно целое число $$$t$$$ ($$$1 \le t \le 2\cdot 10^4$$$) — количество наборов входных данных. Далее следуют описания наборов входных данных.
Первая строка каждого набора содержит два целых числа $$$n$$$ и $$$x$$$ ($$$1 \le x \le n \le 2\cdot 10^5$$$) — длину перестановки и число, которое нужно найти.
Во второй строке через пробел вводится перестановка $$$p$$$ ($$$1 \le p_i \le n$$$).
Гарантируется, что сумма значений $$$n$$$ по всем наборам входных данных не превосходит $$$2\cdot 10^5$$$.
Для каждого набора входных данных выведите в первой строке целое число $$$k$$$ ($$$0 \le k \le 2$$$) — количество совершенных вами операций. В следующих $$$k$$$ строках через пробел выведите по $$$2$$$ целых числа $$$i$$$, $$$j$$$ ($$$1 \le i, j \le n$$$) означающих, что вы меняете местами элементы на позициях $$$i$$$ и $$$j$$$.
Обратите внимание, что вам не нужно минимизировать количество операций.
56 31 2 3 4 5 66 53 1 6 5 2 45 13 5 4 2 16 34 3 1 5 2 63 23 2 1
0 1 3 4 2 2 4 1 5 2 4 5 2 4 1 1 3
Название |
---|