P13609 [NWRRC 2022] Limited Swaps

Lina 正在玩一排 $n$ 个方块。每个方块上写有一个从 $1$ 到 $n$ 的整数。每个整数从 $1$ 到 $n$ 恰好出现一次。 最初，这些方块从左到右的数字依次为 $a_1, a_2, \ldots, a_n$。Lina 希望将这些方块从左到右的数字变为 $b_1, b_2, \ldots, b_n$。 Lina 可以交换任意两个相邻的方块，但只有当它们上面的数字之差至少为 $2$ 时才能交换。这个操作最多可以执行 $20\,000$ 次。 请你找出一种交换序列，将初始排列变为目标排列，或者判断是否不可能完成。

第一行包含一个整数 $n$，表示方块的数量（$1 \le n \le 100$）。 第二行包含 $n$ 个互不相同的整数 $a_1, a_2, \ldots, a_n$，表示初始排列（$1 \le a_i \le n$）。 第三行包含 $n$ 个互不相同的整数 $b_1, b_2, \ldots, b_n$，表示目标排列（$1 \le b_i \le n$）。

如果无法通过允许的操作将初始排列变为目标排列，输出一行 $-1$。 否则，第一行输出一个整数 $k$，表示操作次数（$0 \le k \le 20\,000$）。 第二行输出 $k$ 个整数 $s_1, s_2, \ldots, s_k$，依次表示每次操作（$1 \le s_i \le n-1$）。其中 $s_i$ 表示将第 $s_i$ 个方块与第 $s_i+1$ 个方块交换。 你不需要输出最短的方案。只要满足条件的方案都可以被接受。

在第一个样例中，数字的排列变化如下： $1$ $\underline{3\ 5}$ $2$ $4$ $\rightarrow$ $\underline{1\ 5}$ $3$ $2$ $4$ $\rightarrow$ $5$ $\underline{1\ 3}$ $2$ $4$ $\rightarrow$ $5$ $3$ $1$ $\underline{2\ 4}$ $\rightarrow$ $\underline{5\ 3}$ $1$ $4$ $2$ $\rightarrow$ $3$ $5$ $1$ $4$ $2$ 在第二个样例中，初始排列中甚至无法进行一次合法的交换。 由 ChatGPT 4.1 翻译