← 返回题目列表

Codeforces · 1647/E

E. 小圆和六年级学生

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

在五年级学生取得了最惊人的成功之后,小圆被信任负责教授六年级学生。

她的教室里有 $$$n$$$ 单人课桌。一开始小圆决定学生编号$$$b_i$$$ ($$$1 \le b_i \le n$$$) 坐在编号$$$i$$$ 的课桌上。还有无数编号为 $$$n + 1、n + 2、n + 3、\ldots$$$ 的学生在门口等候,希望能够向小圆本人学到一些东西。请注意,每个学生都有自己独特的编号。

每节课结束后,将按顺序发生以下情况。

1. 坐在课桌$$$i$$$ 的学生移动到课桌$$$p_i$$$。所有学生同时移动。
2. 如果一张桌子上有超过一名学生,则人数最少的学生保留该位置,其他学生将永远从班级中删除。
3. 对于所有空课桌,按升序排列,由外线编号最低的学生占用课桌。

请注意,最后每张桌子上又只有一名学生。保证 $$$p$$$ 的数字使得每节课后至少有一名学生被删除。查看第一个示例的解释以获得更好的理解。

几节课(可能是零节课)后,桌子 $$$i$$$ 被学生 $$$a_i$$$ 占据。给定值 $$$a_1、a_2、\ldots、a_n$$$ 和 $$$p_1、p_2、\ldots、p_n$$$,找到字典顺序最小的合适初始座位排列 $$$b_1、b_2、\ldots、b_n$$$。

排列是 $$$n$$$ 个不同整数的数组,从 $$$1$$$ 到 $$$n$$$,顺序任意。例如,$$$[2,3,1,5,4]$$$ 是一个排列,但 $$$[1,2,2]$$$ 不是($$$2$$$ 出现两次)。 $$$[1,3,4]$$$ 也不是排列($$$n=3$$$ 但数组中有 $$$4$$$)。

对于相同长度的两个不同排列 $$$a$$$ 和 $$$b$$$,如果在 $$$a$$$ 和 $$$b$$$ 不同的第一个位置,排列 $$$a$$$ 的元素比 $$$b$$$ 中的对应元素小,则 $$$a$$$ 按字典顺序小于 $$$b$$$。

输入

输入数据的第一行包含一个整数 $$$n$$$ ($$$2 \le n \le 10^5$$$) — 教室中的课桌数量。

第二行包含 $$$n$$$ 整数 $$$p_1, p_2, \ldots, p_n$$$ ($$$1 \leq p_i \leq n$$$) — 学生移动的课桌。保证 $$$p$$$ 至少有两个相等的元素。

第三行包含 $$$n$$$ 整数 $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \leq a_i \leq 10^9$$$) — 学生的最终座位。保证存在一个初始排列,从中可以获得座位$$$a$$$。

输出

在唯一的行中打印 $$$n$$$ 整数 $$$b_1, b_2, \ldots, b_n$$$ ($$$1 \le b_i \le n$$$) - 按字典顺序描述六年级学生的初始座位的最小排列,可以导致最终座位 $$$a$$$。

示例

输入 #1

5
5 5 3 3 1
1 8 2 9 4

输出 #1

1 3 2 5 4

输入 #2

5
1 3 2 5 2
3 2 5 4 1

输出 #2

3 2 5 4 1

输入 #3

10
10 8 5 3 7 8 6 6 1 1
5 26 24 27 21 4 18 2 28 1

输出 #3

5 4 2 6 7 8 3 9 1 10

注意

第一个测试的描述如下:

第一张图显示了起始排列,这就是答案。然后坐在 $$$1, 2$$$ 课桌的学生被转移到 $$$5$$$ 课桌。此外,一名 $$$1$$$ 学生从 $$$5$$$ 课桌移动,而一名学生从 $$$4$$$ 磁盘转移到 $$$3$$$ 课桌。

因此,在所有这些传输之后,获得了第二幅图像中所示的排列。然后,在编号为$$$5$$$的课桌上,编号为$$$3$$$的学生被开除,在编号为$$$3$$$的课桌上,编号为$$$5$$$的学生被开除。 (因为他们的编号不是最小的)然后编号为 $$$6, 7$$$ 的新生坐在编号为 $$$2, 4$$$ 的课桌旁。第三张图片显示了这种排列(第一课结束后)。

$$$4$$$ 图片显示了第二节课之后所有多余座位被踢出之前的座位安排。第五张显示 $$$2$$$ 课后的最终座位。