今年生日的時候Petya得到了一個序列作為他的生日禮物,可是他不喜歡那個序列的排列方式。現在給你Petya喜歡的序列以及他獲得的序列,請輸入最少要多少次操作才可以變成他喜歡的序列?一個操作定義為將任意兩個元素互換位置一次。如果兩個序列的長度不一樣,請輸出-1
。
輸入有兩行,每行有一些正整數,從1開始連續正整數的排列。第一行是Petya喜歡的序列,第二行是他的生日禮物。數字與數字間用空格隔開,最後一個數字後直接是換行符號。
以下以$N$代表兩序列中較長的那個的長度。
子任務(測資) | 額外限制 | 分數 |
---|---|---|
1(0~9) | $N \leq 10$ | 9 |
2(0~27) | $N \leq 3000$ | 23 |
3(0~49) | $N \leq 1000000$ | 60 |
4(0~56) | $N \leq 2000000$ | 5 |
5(0~63) | $N \leq 3000000$ | 3 |
請輸出一個整數代表最小操作次數。
你以為你來到了Codeforces了嗎?
建國中學106學年度校隊補選pE
2020.11.12 放寬後兩個subtask的時限
No. | Testdata Range | Score |
---|---|---|
1 | 0~9 | 9 |
2 | 0~27 | 23 |
3 | 0~49 | 60 |
4 | 0~56 | 5 |
5 | 0~63 | 3 |
No. | Time Limit (ms) | Memory Limit (KiB) | Output Limit (KiB) | Subtasks |
---|---|---|---|---|
0 | 499 | 131072 | 262144 | |
1 | 499 | 131072 | 262144 | |
2 | 499 | 131072 | 262144 | |
3 | 499 | 131072 | 262144 | |
4 | 499 | 131072 | 262144 | |
5 | 499 | 131072 | 262144 | |
6 | 499 | 131072 | 262144 | |
7 | 499 | 131072 | 262144 | |
8 | 499 | 131072 | 262144 | |
9 | 499 | 131072 | 262144 | |
10 | 499 | 131072 | 262144 | |
11 | 499 | 131072 | 262144 | |
12 | 499 | 131072 | 262144 | |
13 | 499 | 131072 | 262144 | |
14 | 499 | 131072 | 262144 | |
15 | 499 | 131072 | 262144 | |
16 | 499 | 131072 | 262144 | |
17 | 499 | 131072 | 262144 | |
18 | 499 | 131072 | 262144 | |
19 | 499 | 131072 | 262144 | |
20 | 499 | 131072 | 262144 | |
21 | 499 | 131072 | 262144 | |
22 | 499 | 131072 | 262144 | |
23 | 499 | 131072 | 262144 | |
24 | 499 | 131072 | 262144 | |
25 | 499 | 131072 | 262144 | |
26 | 499 | 131072 | 262144 | |
27 | 499 | 131072 | 262144 | |
28 | 712 | 131072 | 262144 | |
29 | 712 | 131072 | 262144 | |
30 | 712 | 131072 | 262144 | |
31 | 712 | 131072 | 262144 | |
32 | 712 | 131072 | 262144 | |
33 | 712 | 131072 | 262144 | |
34 | 712 | 131072 | 262144 | |
35 | 712 | 131072 | 262144 | |
36 | 712 | 131072 | 262144 | |
37 | 712 | 131072 | 262144 | |
38 | 712 | 131072 | 262144 | |
39 | 712 | 131072 | 262144 | |
40 | 712 | 131072 | 262144 | |
41 | 712 | 131072 | 262144 | |
42 | 712 | 131072 | 262144 | |
43 | 712 | 131072 | 262144 | |
44 | 712 | 131072 | 262144 | |
45 | 712 | 131072 | 262144 | |
46 | 712 | 131072 | 262144 | |
47 | 712 | 131072 | 262144 | |
48 | 712 | 131072 | 262144 | |
49 | 712 | 131072 | 262144 | |
50 | 999 | 131072 | 262144 | |
51 | 999 | 131072 | 262144 | |
52 | 999 | 131072 | 262144 | |
53 | 999 | 131072 | 262144 | |
54 | 999 | 131072 | 262144 | |
55 | 999 | 131072 | 262144 | |
56 | 999 | 131072 | 262144 | |
57 | 999 | 131072 | 262144 | |
58 | 999 | 131072 | 262144 | |
59 | 999 | 131072 | 262144 | |
60 | 999 | 131072 | 262144 | |
61 | 999 | 131072 | 262144 | |
62 | 999 | 131072 | 262144 | |
63 | 999 | 131072 | 262144 |