问题 H: 林克与翻转排列

问题 H: 林克与翻转排列

时间限制: 1 Sec  内存限制: 128 MB  Special Judge
提交: 49  解决: 13
[状态] [讨论版] [提交] [命题人:]
题目描述
林克穿过果彭加沼泽,来到了壶洞窟的门口。但是一道机关挡住了他的去路,机关上的铭牌刻着:"只有解开迷题的人,方可进入洞窟探寻宝物。"
这个迷题是这样的:机关上有上下两串数字,它们分别是 1∼n 的排列。上方的数字串可以操作,而下方的不行。每次操作可以选取连续的 k 个数字,将它们翻转过来。由于机关有一定的使用寿命,操作至多可以进行  2×105 次,允许不进行任何操作。只有两个序列变得完全相同,门才会开启。
形式化地说,有两个 1∼n的排列a1,a2,⋯,an 和 b1,b2,⋯,bn,每次操作可以选取一个 l,满足 1≤l≤n−k+1,并将子串 al,al+1,⋯,al+k−1 翻转过来。操作之后,a1,a2,⋯,an 会变成 a1,⋯,al−1,al+k−1,⋯,al+1,al,al+k,⋯,an。你需要用若干次操作使得 a1=b1,a2=b2,⋯,an=bn
请你帮助林克破解这道机关。
输入
第一行包含两个整数 n, k (2≤k≤n≤100k 为偶数),含义见题目描述。
第二行包含 n 个整数,第 i 个为 a(1≤ai≤n),表示上方数字串的第 i 个数字。保证所有的 ai 两两不同。
第三行包含 n 个整数,第 i 个为 bi (1≤bi≤n),表示下方数字串的第 i 个数字。保证所有的 bi 两两不同。
输出
如果这道机关无解,输出一行一个整数 −1。
否则输出一种操作的方案。方案第一行,包含一个整数 c,表示操作的次数。c 应当满足 0≤c≤2×105
接下来 c 行,第 i 行包含一个整数 li,表示第 i 步操作翻转了  ali,ali+1,⋯,ali+k−1 这个子串。li 应当满足1≤li≤n−k+1。
如果有多种方案,输出任意一种即可。可以证明,只要有解,必然存在一种不超过 2×105  次操作的方案。
样例输入 Copy
4 2
1 4 2 3
1 2 3 4
样例输出 Copy
2
2
3
提示
样例输入二
6 4 2 5 4 1 6 3 1 2 3 4 5 6
样例输出二
2
第一个样例,a 的变化为 1,4,2,3→1,2,4,3→1,2,3,4。
第二个样例无解。