Checker for Array Shuffling
题意翻译
给定一个长为 $n$ 的数组 $a$。若 $a$ 的一个排列 $b$ 可以通过 $k$ 次将任意两个数交换位置得到 $a$,则 $b$ 的价值为所有合法 $k$ 的最小值。
现在给出 $a$ 的某个排列 $b$,判断它的价值是否为所有长为 $n$ 的数组的最大值。若是则输出 `AC` ,否则输出 `WA` 。$t$ 组数据。
$t\le 10^4$,$n\le 2\cdot 10^5$,$1\le a_i,b_i \le n$。
题目描述
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.
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 \leq i,j \leq n $ .
- Swap $ b_i $ and $ b_j $ .
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 \leq t \leq 10^4 $ ) — 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 \leq n \leq 2 \cdot 10^5 $ ) — the length of the array.
The second line of each test case contains $ n $ integers $ a_1, a_2, \ldots, a_n $ ( $ 1 \leq a_i \leq n $ ) — the elements of the array $ a $ .
The third line of each test case contains $ n $ integers $ b_1, b_2, \ldots, b_n $ ( $ 1 \leq b_i \leq 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 \cdot 10^5 $ .
输出格式
For each test case, print "AC" (without quotes) if $ b $ has the maximum sadness over all permutations of $ a $ , and "WA" (without quotes) otherwise.
输入输出样例
输入样例 #1
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
输出样例 #1
AC
AC
WA
WA
说明
In the first test case, the array $ [1,2] $ has sadness $ 1 $ . We can transform $ [1,2] $ into $ [2,1] $ using one operation with $ (i,j)=(1,2) $ .
In the second test case, the array $ [3,3,2,1] $ has sadness $ 2 $ . We can transform $ [3,3,2,1] $ into $ [1,2,3,3] $ with two operations with $ (i,j)=(1,4) $ and $ (i,j)=(2,3) $ respectively.
In the third test case, the array $ [2,1] $ has sadness $ 0 $ .
In the fourth test case, the array $ [3,2,3,1] $ has sadness $ 1 $ .