← 返回题目列表

AtCoder · abc294_c

F. 合并序列

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

分数: 300 点

问题陈述

给你严格递增的长度序列 N 和 M: A=(A _ 1,A _ 2,\ldots,A _ N) 和 B=(B _ 1,B _ 2,\ldots,B _ M)。 在这里, A _ i\neq B _ j 对于每个 i 和 j (1\leq i\leq N,1\leq j\leq M).

让 C=(C _ 1,C _ 2,\ldots,C _ {N+M}) 是长度严格递增的序列 N+M 由以下过程产生。

  • 让 C 是以下的串联 A 和 B。正式地,让 C _ i=A _ i 为 i=1,2,\ldots,N,和 C _ i=B _ {i-N} 为 i=N+1,N+2,\ldots,N+M.
  • 排序 C 按升序排列。

对于每个 A _ 1,A _ 2,\ldots,A _ N, B _ 1,B _ 2,\ldots,B _ M,找到它的位置 C。 更正式地说,对于每个 i=1,2,\ldots,N,查找 k 这样 C _ k=A _ i,并且对于每个 j=1,2,\ldots,M,查找 k 这样 C _ k=B _ j.

约束

  • 1\leq N,M\leq 10^5
  • 1\leq A _ 1\lt A _ 2\lt\cdots\lt A _ N\leq 10^9
  • 1\leq B _ 1\lt B _ 2\lt\cdots\lt B _ M\leq 10^9
  • A _ i\neq B _ j 对于每个 i 和 j (1\leq i\leq N,1\leq j\leq M).
  • 输入中的所有值都是整数。

输入

输入由标准输入按以下格式给出:

N M
A _ 1 A _ 2 \ldots A _ N
B _ 1 B _ 2 \ldots B _ M

输出

分两行打印答案。
第一行应包含以下位置 A _ 1,A _ 2,\ldots,A _ N in C,中间有空格。
第二行应包含以下位置 B _ 1,B _ 2,\ldots,B _ M in C,中间有空格。


示例输入 1

4 3
3 14 15 92
6 53 58

示例输出 1

1 3 4 7
2 5 6

C 将是 (3,6,14,15,53,58,92)。 在这里, 1-st, 3-rd, 4-th, 7第一个元素来自 A=(3,14,15,92),以及 2-nd, 5-th, 6第一个元素来自 B=(6,53,58).


示例输入 2

4 4
1 2 3 4
100 200 300 400

示例输出 2

1 2 3 4
5 6 7 8

示例输入 3

8 12
3 4 10 15 17 18 22 30
5 7 11 13 14 16 19 21 23 24 27 28

示例输出 3

1 2 5 9 11 12 15 20
3 4 6 7 8 10 13 14 16 17 18 19