[Solution] Checker for Array Shuffling solution codeforces

Checker for Array Shuffling solution codeforces – oolimry has an array 𝑎a of length 𝑛n which he really likes. Today, you have changed his array to 𝑏b, a permutation of 𝑎a, to make him sad.

[Solution] Checker for Array Shuffling solution codeforces

Because oolimry is only a duck, he can only perform the following operation to restore his array:

  • Choose two integers 𝑖,𝑗i,j such that 1𝑖,𝑗𝑛1≤i,j≤n.
  • Swap 𝑏𝑖bi and 𝑏𝑗bj.

The sadness of the array 𝑏b is the minimum number of operations needed to transform 𝑏b into 𝑎a.

Given the arrays 𝑎a and 𝑏b, where 𝑏b is a permutation of 𝑎a, determine if 𝑏b has the maximum sadness over all permutations of 𝑎a.

Input

Each test contains multiple test cases. The first line contains a single integer 𝑡t (1𝑡1041≤t≤104)  — the number of test cases. The description of the test cases follows.

The first line of each test case contains a single integer 𝑛n (1𝑛21051≤n≤2⋅105)  — the length of the array.

The second line of each test case contains 𝑛n integers 𝑎1,𝑎2,,𝑎𝑛a1,a2,…,an (1𝑎𝑖𝑛1≤ai≤n)  — the elements of the array 𝑎a.

The third line of each test case contains 𝑛n integers 𝑏1,𝑏2,,𝑏𝑛b1,b2,…,bn (1𝑏𝑖𝑛1≤bi≤n)  — the elements of the array 𝑏b.

It is guaranteed that 𝑏b is a permutation of 𝑎a.

It is guaranteed that the sum of 𝑛n over all test cases does not exceed 21052⋅105.

[Solution] Checker for Array Shuffling solution codeforces

For each test case, print “AC” (without quotes) if 𝑏b has the maximum sadness over all permutations of 𝑎a, and “WA” (without quotes) otherwise.

Example
input

Copy
4
2
2 1
1 2
4
1 2 3 3
3 3 2 1
2
2 1
2 1
4
1 2 3 3
3 2 3 1
output

Copy
AC
AC
WA
WA

Checker for Array Shuffling solution codeforces

In the first test case, the array [1,2][1,2] has sadness 11. We can transform [1,2][1,2] into [2,1][2,1] using one operation with (𝑖,𝑗)=(1,2)(i,j)=(1,2).

In the second test case, the array [3,3,2,1][3,3,2,1] has sadness 22. We can transform [3,3,2,1][3,3,2,1] into [1,2,3,3][1,2,3,3] with two operations with (𝑖,𝑗)=(1,4)(i,j)=(1,4) and (𝑖,𝑗)=(2,3)(i,j)=(2,3) respectively.

In the third test case, the array [2,1][2,1] has sadness 00.

In the fourth test case, the array [3,2,3,1][3,2,3,1] has sadness 11.

 

For Solution

Click here

Leave a Comment