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.
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≤𝑛≤2⋅1051≤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 2⋅1052⋅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.
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
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.