← 返回题目列表

AtCoder · tupc2022_h

H. 下一个排列

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

配点 : {300} 点

問題文

(1,2,\ldots,N) 的排列在下文中将简称为排列。

順列 P 对于 \mathrm{NextPermutation} (P) 定义如下。 您将获得

  • P=(N,N-1,\ldots,2,1) 什么时候 (1,2,\ldots,N-1,N)
  • 否则,长度为 N 的所有排列按字典序升序排列时 P 紧随其后的那个

2 个排列 P=(P_1, P_2, \ldots,P_N), Q=(Q_1, Q_2, \ldots, Q_N) 。 对于

P 是 在 (1,2,\ldots, N-1,N) 重复以下操作,直到匹配

  • P 该值应乘以 \mathrm{NextPermutation} (P) 在,Q 该值应乘以 \mathrm{NextPermutation} (Q) 。

决赛 Q 。

制約

  • 2\leq N\leq 2\times 10^5
  • (P_1, P_2, \ldots,P_N),(Q_1, Q_2, \ldots, Q_N) 是 您也可以写 (1,2,\ldots,N) 的排列 给出了
  • 所有输入均为整数

入力

输入是按以下格式从标准输入给出的。

N
P_1 P_2 \ldots P_N
Q_1 Q_2 \ldots Q_N

出力

所要求的排列为 Q'=(Q'_1,Q'_2,\ldots,Q'_N) , Q'_1,Q'_2,\ldots,Q'_N 以空格分隔的顺序在一行中输出。


入力例 1

3
2 3 1
3 2 1

出力例 1

2 1 3

通过操作 P,Q 如下所示变化:

  • P:(2,3,1)\to (3,1,2)\to (3,2,1)\to (1,2,3)
  • Q:(3,2,1)\to (1,2,3)\to (1,3,2)\to (2,1,3)

入力例 2

4
4 2 1 3
2 1 3 4

出力例 2

2 4 1 3

通过操作 P,Q 如下所示变化:

  • P:(4,2,1,3)\to (4,2,3,1)\to (4,3,1,2)\to (4,3,2,1)\to(1,2,3,4)
  • Q:(2,1,3,4)\to(2,1,4,3)\to(2,3,1,4)\to(2,3,4,1)\to(2,4,1,3)

入力例 3

4
1 2 3 4
1 2 3 4

出力例 3

1 2 3 4

一次操作都不执行。