分数: 700 点
问题陈述
给定长度的整数序列 N, A = (A_1, \dots ,A_N) 和 B = (B_1, \dots ,B_N),和一个正整数 K.
每次您支付费用 1,可以执行相邻交换 正是 K 次。相邻交换是指以下操作:
- 选择一个整数 i 之间 1 和 N-1,包含在内,并交换 A_i 和 A_{i+1}.
确定是否可以使 A 匹配 B。如果可能的话,找出使它们匹配所需的最低成本。
你被给予 T 测试用例;为他们每个人找到答案。
约束
- 1 \le T \le 10^5
- 2 \le N \le 3 \times 10^5
- 1 \le K \le 10^9
- 1 \le A_i,B_i \le N
- \{A_1,\dots ,A_N\} 和 \{B_1,\dots ,B_N\} 匹配为多重集。
- 总和 N 所有测试用例最多 3 \times 10^5.
- 所有输入值均为整数。
输入
输入由标准输入按以下格式给出:
T
\text{case}_1
\text{case}_2
\vdots
\text{case}_T
每个测试用例均按以下格式给出:
N K A_1 A_2 \ldots A_N B_1 B_2 \ldots B_N
输出
输出 T 行。
的 i如果可以的话,第行应该包含最小成本 A 匹配 B 为 i第一个测试用例,以及 -1 否则。
示例输入 1
3 5 4 3 1 4 1 5 5 1 3 1 4 2 1000000000 1 2 2 1 10 13 1 2 3 4 5 6 7 8 9 10 10 9 8 7 6 5 4 3 2 1
示例输出 1
2 -1 5
对于第一个测试用例,可以使 A 和 B 匹配成本为 2 通过执行以下操作:
- 支付费用 1,然后选择 i as 3,1,4,1 为了每个相邻的交换,使得 A = (3,1,1,5,4).
- 支付费用 1,然后选择 i as 3,1,2,1 为了每个相邻的交换,使得 A = (5,1,3,1,4).
对于第二个测试用例,不可能使 A 和 B 无论成本如何,都会匹配。