分数: 575 点
问题陈述
给你排列 P = (P_1, P_2, \ldots, P_N) 和 A = (A_1, A_2, \ldots, A_N) of (1,2,\ldots,N).
您可以执行以下操作任意次数,可能为零:
- 替换 A_i 与 A_{P_i} 同时 对于所有人 i=1,2,\ldots,N.
打印字典顺序最小的 可以获得 A 。
什么是字典顺序?
对于长度序列 N, A = (A_1, A_2, \ldots, A_N) 和 B = (B_1, B_2, \ldots, B_N), A 按字典顺序小于 B 当且仅当:
- 存在一个整数 i\ (1\leq i\leq N) 这样 A_i < B_i,和 A_j = B_j 对于所有人 1\leq j < i.
约束
- 1\leq N\leq2\times10^5
- 1\leq P_i\leq N\ (1\leq i\leq N)
- P_i\neq P_j\ (1\leq i<j\leq N)
- 1\leq A_i\leq N\ (1\leq i\leq N)
- A_i\neq A_j\ (1\leq i<j\leq N)
- 所有输入值均为整数。
输入
输入由标准输入按以下格式给出:
N P_1 P_2 \ldots P_N A_1 A_2 \ldots A_N
输出
让 (A_1, A_2, \ldots, A_N) 是字典顺序最小的 可以获得 A 。打印 A_1, A_2, \ldots, A_N 按此顺序,用空格分隔,一行。
示例输入 1
6 3 1 5 6 2 4 4 3 1 6 2 5
示例输出 1
1 4 2 5 3 6
最初, A = (4, 3, 1, 6, 2, 5).
重复该操作会产生以下结果。
- A = (1, 4, 2, 5, 3, 6)
- A = (2, 1, 3, 6, 4, 5)
- A = (3, 2, 4, 5, 1, 6)
- A = (4, 3, 1, 6, 2, 5)
此后, A 每四次操作就会恢复到原始状态。
因此,打印其中按字典顺序最小的,即 1 4 2 5 3 6.
示例输入 2
8 3 5 8 7 2 6 1 4 1 2 3 4 5 6 7 8
示例输出 2
1 2 3 4 5 6 7 8
您可以选择不执行任何操作。
示例输入 3
26 24 14 4 20 15 19 16 11 23 22 12 18 21 3 6 8 26 2 25 7 13 1 5 9 17 10 15 3 10 1 13 19 22 24 20 4 14 23 7 26 25 18 11 6 9 12 2 21 5 16 8 17
示例输出 3
4 1 22 18 20 13 14 6 15 11 3 26 2 12 5 23 9 10 25 24 7 17 16 21 19 8