28723번 - Перестроения 스페셜 저지다국어
| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 2 초 | 1024 MB | 10 | 5 | 4 | 57.143% |
문제
Для победы над злобным клоуном в финальном сражении, Майк созвал всех своих друзей. Осталось только определиться с тактикой ведения боя, и победа в кармане.
Всего в бою будет участвовать $n$ друзей. Для эффективности ведения боя пронумеруем их от $1$ до $n$. Исходно друзья выстроились в ряд, причем на $i$-е место в ряду встал друг с номером $a_i$. После долгих размышлений, Майк пришел к выводу, что наиболее эффективное расположение друзей будет достигнуто, если на $i$-м месте в ряду будет стоять друг с номером $b_i$.
Для того, чтобы изменить порядок друзей в ряду, Майк может совершить несколько перестроений. Каждое перестроение происходит следующим образом: Майк выбирает некоторое непустое подмножество друзей, после чего эти друзья выходят из ряда и встают в его начало в порядке, обратном тому, в котором они стояли исходно. При этом порядок друзей, которые остались стоять в ряду, не меняется.
Например, если друзья стояли в порядке $3, 4, 7, 6, 2, 5, 1$, а Майк выбрал друзей с номерами $4, 7, 5$, после перестроения друзья будут стоять в порядке $5, 7, 4, 3, 6, 2, 1$.
Бой с Пеннивайзом начнется довольно скоро, поэтому Майк хочет расположить друзей в желаемом порядке не более, чем за $15$ перестроений. Помогите ему справиться с этой задачей!
Обратите внимание, что минимизировать количество перестроений не требуется. Гарантируется, что, за не более чем $15$ перестроений, добиться желаемого порядка возможно.
입력
В первой строке дано одно целое число $n$ --- количество друзей в ряду ($1 \le n \le 10\,000$).
Вторая строка содержит $n$ различных целых чисел $a_i$ от $1$ до $n$ --- исходный порядок друзей в ряду ($1 \le a_i \le n$). Третья строка содержит $n$ различных целых чисел $b_i$ от $1$ до $n$ --- желаемый порядок друзей в ряду ($1 \le b_i \le n$).
출력
В первой строке выведите целое число $k$ ($0 \le k \le 15$) --- количество перестроений в найденном решении. В каждой из следующих $k$ строк выведите описание перестроений, которые необходимо совершить. Для каждого перестроения сначала выведите число $c_i$ --- количество друзей, которые должны выйти из ряда ($1 \le c_i \le n$), а затем $c_i$ различных целых чисел от $1$ до $n$ --- номера друзей, которые должны выйти из ряда. Номера можно выводить в произвольном порядке.
예제 입력 1
5 5 4 3 2 1 3 4 5 1 2
예제 출력 1
4 5 1 2 3 4 5 1 5 1 4 1 3
예제 입력 2
7 3 4 7 6 2 5 1 2 6 3 4 5 7 1
예제 출력 2
3 3 6 5 7 3 3 4 5 3 2 6 3
노트
В первом тесте порядок друзей изменяется следующим образом:
$5, 4, 3, 2, 1 \rightarrow 1, 2, 3, 4, 5 \rightarrow 5, 1, 2, 3, 4 \rightarrow 4, 5, 1, 2, 3 \rightarrow 3, 4, 5, 1, 2$
Во втором тесте порядок друзей изменяется следующим образом:
$3, 4, 7, 6, 2, 5, 1 \rightarrow 5, 6, 7, 3, 4, 2, 1 \rightarrow 4, 3, 5, 6, 7, 2, 1 \rightarrow 2, 6, 3, 4, 5, 7, 1$