← 返回题目列表

AtCoder · tenka1_2013_final_b

B. 天下一魔法

中文机器翻译题面 查看原题

問題文

一家公司的总裁高桥决定表演魔术来娱乐他的员工。 为了成功地表演魔术,你必须在员工不注意的情况下快速对看似随机的卡片进行排序。

要使用的卡片数量2N+1始终是奇数,为了方便起见,每张卡都 来自号码1假设写入数字2N+1。 下一个是高桥君2连续执行以下操作来重新排列卡片。 然而, 小于X是 给出了1以上2N+1的一组整数。

操作1(剪切):
集合X的元素 选择K并从卡的开头开始。K取出卡片,按照相同的顺序放在卡片的末尾。 例如, 如果K=3,则使用此操作[[5, 1, 4, 7, 6, 2, 3] → [7, 6, 2, 3, 5, 1, 4]。

操作2(里福洗牌):
从卡开始N+1卡和剩余的 分为N卡, 从一开始1轮流一张一张地拿牌。此时,最初 从一组N+1卡片中取出。 例如,通过此操作 [5, 1, 4, 7, 6, 2, 3] → [5, 6, 1, 2, 4, 3, 7]。

卡片的初始排列和收集 给定X,求高桥按照升序重新排列卡片所需的最少操作次数。 但是,如果无法将卡片完全按升序排序, 打印-1。


入力

输入是按以下格式从标准输入给出的。

N M
C_1 C_2 ‥‥ C_{2N+1}
K_1 K_2 ‥‥ K_M
  • 输入是 有一行3。
  • 1行中,N并设置X中的元素数量M用空格分隔。
  • 2行表示卡片的初始排列。2N+1整数由空格分隔。
    • i第一个整数C_i从头开始 代表写在第i卡上的数字。
    • 该卡有1假设一直下雨,直到2N+1之前的整数正好是 写了1次。
  • 3该套 作为X的元素 在行M整数由空格分隔。
    • i第一个整数K_i是 给出了1≦K_i<2N+1满意。
    • 3中,相同的整数是 不能给予超过2次。 对于
    • M=0,3该行将为空行(仅换行)。

部分点

  • 1≦N≦4、X=\{1\}(M=1、K_1=1) 如果您回答正确,200 作为满分的部分分数,20 点。
  • 1≦N≦2013、X=\{1\}(M=1、K_1=1) 如果您回答正确,200 与上述分开,作为满分的部分分数。 如果您正确回答 80点。
  • 0≦N≦2013、0≦M<2N+1,200 剩下的点是 100 点。

出力

将按升序对卡片进行排序所需的最少操作数打印到标准输出。1行。
但是,如果卡片无法按升序排序,则改为最小操作数 输出-1。
请在末尾输出换行符。


入力例 1

1 1
3 2 1
1

出力例 1

2
  • 例如,通过执行以下操作,您可以使用最少的操作数按升序排序。 执行
    • 操作2。 [ 操作为3, 2, 1] → [3, 1, 2]
    • K=1作为1。 [ 操作为3, 1, 2] → [1, 2, 3]

入力例 2

2 1
3 2 5 1 4
1

出力例 2

-1
  • 在这种情况下,无论您做什么都无法按升序排序。

入力例 3

2 1
4 2 5 3 1
1

出力例 3

4
  • 例如,通过执行以下操作,您可以使用最少的操作数按升序排序。 执行
    • 操作2。 [ 操作为4, 2, 5, 3, 1] → [4, 3, 2, 1, 5]
    • 操作2。 [ 操作为4, 3, 2, 1, 5] → [4, 1, 3, 5, 2]
    • K=1作为1。 [ 操作为4, 1, 3, 5, 2] → [1, 3, 5, 2, 4]
    • 操作2。 [ 操作为1, 3, 5, 2, 4] → [1, 2, 3, 4, 5]

入力例 4

3 1
1 2 3 4 5 6 7
1

出力例 4

0
  • 由于顺序是从头开始升序,因此所需的最少操作次数为0。


入力例 5

4 2
2 3 4 5 6 7 8 9 1
1 6

出力例 5

3
  • 例如,通过执行以下操作,您可以使用最少的操作数按升序排序。 执行
    • K=1作为1。 [ 操作为2, 3, 4, 5, 6, 7, 8, 9, 1] → [3, 4, 5, 6, 7, 8, 9, 1, 2]
    • K=6作为1。 [ 操作为3, 4, 5, 6, 7, 8, 9, 1, 2] → [9, 1, 2, 3, 4, 5, 6, 7, 8]
    • K=1作为1。 [ 操作为9, 1, 2, 3, 4, 5, 6, 7, 8] → [1, 2, 3, 4, 5, 6, 7, 8, 9]