2033 . Petya and Array

Submit
Status
Discussion / Solution
Ranklist
Back to Problems List

TopCoder

Caido
$\mathbb{W}\mathcal{aimai}\sim$

User's AC Ratio

69.2% (27/39)

Submission's AC Ratio

34.7% (243/701)

Tags

CKcon 2018-CKcon-sup

Description

今年生日的時候Petya得到了一個序列作為他的生日禮物，可是他不喜歡那個序列的排列方式。現在給你Petya喜歡的序列以及他獲得的序列，請輸入最少要多少次操作才可以變成他喜歡的序列？一個操作定義為將任意兩個元素互換位置一次。如果兩個序列的長度不一樣，請輸出-1。

Input Format

輸入有兩行，每行有一些正整數，從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

Output Format

請輸出一個整數代表最小操作次數。

Sample Input 1

1 2
2 1

Sample Output 1

1

Hints

你以為你來到了Codeforces了嗎？

Problem Source

建國中學106學年度校隊補選pE
2020.11.12 放寬後兩個subtask的時限

Subtasks

No. Testdata Range Score
1 0~9 9
2 0~27 23
3 0~49 60
4 0~56 5
5 0~63 3

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 499 131072 262144 1 2 3 4 5
1 499 131072 262144 1 2 3 4 5
2 499 131072 262144 1 2 3 4 5
3 499 131072 262144 1 2 3 4 5
4 499 131072 262144 1 2 3 4 5
5 499 131072 262144 1 2 3 4 5
6 499 131072 262144 1 2 3 4 5
7 499 131072 262144 1 2 3 4 5
8 499 131072 262144 1 2 3 4 5
9 499 131072 262144 1 2 3 4 5
10 499 131072 262144 2 3 4 5
11 499 131072 262144 2 3 4 5
12 499 131072 262144 2 3 4 5
13 499 131072 262144 2 3 4 5
14 499 131072 262144 2 3 4 5
15 499 131072 262144 2 3 4 5
16 499 131072 262144 2 3 4 5
17 499 131072 262144 2 3 4 5
18 499 131072 262144 2 3 4 5
19 499 131072 262144 2 3 4 5
20 499 131072 262144 2 3 4 5
21 499 131072 262144 2 3 4 5
22 499 131072 262144 2 3 4 5
23 499 131072 262144 2 3 4 5
24 499 131072 262144 2 3 4 5
25 499 131072 262144 2 3 4 5
26 499 131072 262144 2 3 4 5
27 499 131072 262144 2 3 4 5
28 712 131072 262144 3 4 5
29 712 131072 262144 3 4 5
30 712 131072 262144 3 4 5
31 712 131072 262144 3 4 5
32 712 131072 262144 3 4 5
33 712 131072 262144 3 4 5
34 712 131072 262144 3 4 5
35 712 131072 262144 3 4 5
36 712 131072 262144 3 4 5
37 712 131072 262144 3 4 5
38 712 131072 262144 3 4 5
39 712 131072 262144 3 4 5
40 712 131072 262144 3 4 5
41 712 131072 262144 3 4 5
42 712 131072 262144 3 4 5
43 712 131072 262144 3 4 5
44 712 131072 262144 3 4 5
45 712 131072 262144 3 4 5
46 712 131072 262144 3 4 5
47 712 131072 262144 3 4 5
48 712 131072 262144 3 4 5
49 712 131072 262144 3 4 5
50 999 131072 262144 4 5
51 999 131072 262144 4 5
52 999 131072 262144 4 5
53 999 131072 262144 4 5
54 999 131072 262144 4 5
55 999 131072 262144 4 5
56 999 131072 262144 4 5
57 999 131072 262144 5
58 999 131072 262144 5
59 999 131072 262144 5
60 999 131072 262144 5
61 999 131072 262144 5
62 999 131072 262144 5
63 999 131072 262144 5
Submit
Back to Top