1450 . 又是一道簡單題
TopCoder
Tags
Description
我們說一個長度為 $M$ 的序列 $P$ 是一個排列若 $1, 2, \ldots, M$ 在 $P$ 中各出現恰一次。
對於兩個長度為 $M$ 的排列 $P, Q$，定義 $P \circ Q$ 為序列 $P_{Q_1}, P_{Q_2}, \ldots, P_{Q_M}$。注意到 $P \circ Q$ 依然是一個排列。
定義一個長度為 $M$ 的排列 $P$ 的不動程度為 $1\le i\le M$ 中，滿足 $P_i = i$ 的個數。
給定一個正整數 $N$ 和兩個長度為 $N$ 的排列 $A, B$ 其中對於所有 $1\le i\le N$，$A_i,B_i,i$ 互不相同。你的任務是找到一個排列 $C$ 使得 $A \circ C, B\circ C, C$ 這三個排列的不動程度總和最小。
Input Format
輸入第一行只有一個正整數 $T$，代表子測試資料個數。
對於每個子測試資料，輸入三行：
第一行只有一個正整數 $N$，代表排列長度。
第二行有 $N$ 個正整數 $A_1, A_2, \ldots, A_N$，代表排列 $A$。
第三行有 $N$ 個正整數 $B_1, B_2, \ldots, B_N$，代表排列 $B$。
- $1\le T\le 5000$
- $3\le N\le 5000$
- $1\le A_i, B_i \le N$
- $\forall 1\le i < j\le N, A_i\neq A_j$
- $\forall i\le i < j\le N, B_i\neq B_j$
- $\forall 1\le i\le N, A_i\neq i, B_i\neq i, A_i\neq B_i$
- 保證 $N$ 的總和不超過 $25000$。
Output Format
每個子測試資料輸出兩行。
第一行輸出一個整數 $X$，代表 $A\circ C, B\circ C, C$ 的不動程度總和最小值。
第二行輸出 $N$ 個正整數 $C_1, C_2, \ldots, C_N$，代表一個達到上述最小值的排列 $C$。如果有多種排列能達到最小值，輸出任意一個即可。
- $1 \le C_i \le N$
- $\forall 1\le i < j \le N, C_i\neq C_j$
Sample Input 1
2 3 2 3 1 3 1 2 7 2 3 4 5 6 7 1 7 6 5 1 3 2 4
Sample Output 1
3 1 2 3 0 2 3 1 5 6 7 4
Hints
Problem Source
Subtasks
| No. | Testdata Range | Constraints | Score |
|---|---|---|---|
| 1 | 0 | 範例測資。 | 0 |
| 2 | 0~20 | 無特別限制。 | 100 |