← 返回题目列表

AtCoder · abc371_g

G. 字典顺序最小排列

中文机器翻译题面 查看原题

分数: 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