E - Swap K times 解説 /

実行時間制限: 2 sec / メモリ制限: 1024 MiB

配点 : 700 点

問題文

長さ N の整数列 A = (A_1, \dots ,A_N), B = (B_1, \dots ,B_N) と正整数 K が与えられます。

コストを 1 払うたびに、隣接 swap をちょうど K 回行うことが出来ます。隣接 swap とは、以下の操作を指します。

  • 1 以上 N-1 以下の整数 i を 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 行目には i 番目のテストケースについて、A を B に一致させられる場合は最小コストを、そうでない場合は -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

1 つ目のテストケースについて、以下のような操作を行うことで、2 のコストで A と B を一致させることが出来ます。

  1. コストを 1 払い、各隣接 swap における i を 3,1,4,1 の順で選ぶことで A = (3,1,1,5,4) となる。
  2. コストを 1 払い、各隣接 swap における i を 3,1,2,1 の順で選ぶことで A = (5,1,3,1,4) となる。

2 つ目のテストケースについて、コストによらず、A と B を一致させることは出来ません。

Score : 700 points

Problem Statement

You are given integer sequences of length N, A = (A_1, \dots ,A_N) and B = (B_1, \dots ,B_N), and a positive integer K.

Each time you pay a cost of 1, you can perform adjacent swaps exactly K times. An adjacent swap refers to the following operation:

  • Choose an integer i between 1 and N-1, inclusive, and swap A_i and A_{i+1}.

Determine if it is possible to make A match B. If possible, find the minimum cost required to make them match.

You are given T test cases; find the answer for each of them.

Constraints

  • 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\} and \{B_1,\dots ,B_N\} match as multisets.
  • The sum of N over all test cases is at most 3 \times 10^5.
  • All input values are integers.

Input

The input is given from Standard Input in the following format:

T
\text{case}_1
\text{case}_2
\vdots
\text{case}_T

Each test case is given in the following format:

N K
A_1 A_2 \ldots A_N
B_1 B_2 \ldots B_N

Output

Output T lines.

The i-th line should contain the minimum cost if it is possible to make A match B for the i-th test case, and -1 otherwise.

Sample Input 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

Sample Output 1

2
-1
5

For the first test case, it is possible to make A and B match with a cost of 2 by performing the following operations:

  1. Pay a cost of 1, and choose i as 3,1,4,1 in order for each adjacent swap, making A = (3,1,1,5,4).
  2. Pay a cost of 1, and choose i as 3,1,2,1 in order for each adjacent swap, making A = (5,1,3,1,4).

For the second test case, it is impossible to make A and B match regardless of the cost.