HM261 有序求交

来源： 第 261 集 常用集合算法-set_intersection

难度： 普及-

时间限制： 1s

空间限制： 64MB

题目描述

集合算法有三个：交集 set_intersection、并集 set_union、差集 set_difference。本题求交集：两个有序容器里**两边都出现**的那些值（重复的那一段）。例如一段是 \(0\sim 9\)，另一段是 \(5\sim 14\)，交集是 \(5\,6\,7\,8\,9\)。

五个参数：第一段起止迭代器、第二段起止迭代器、目标容器起始迭代器。算法在算法头文件中。必须同时满足：

1. 两个原容器都已有序，且方向一致，否则结果不对。输入可能无序，先各自排成升序。
2. 目标容器要提前 resize。最坏情况是一段完全被另一段包含，交集长度等于较短那段，因此容量取 min（两段长度）。min 也在算法头文件中。两段完全不相交时，多出来的位置保持默认 \(0\)。
3. 算法返回「交集真正结束」的迭代器。遍历交集必须用这个返回值，不能用目标容器的 end()，否则会把后面补的 \(0\) 也扫出来。

先输出用返回迭代器截出来的交集；再输出从目标起始扫到 end() 的整段（含补零），对照为何不能扫到 end()。

输入格式

第一行一个整数 \(n\)。

第二行 \(n\) 个整数。当 \(n=0\) 时本行可以是空行。

第三行一个整数 \(m\)。

第四行 \(m\) 个整数。当 \(m=0\) 时本行可以是空行。

输出格式

共两行：

1. 交集（用返回迭代器截断）；
2. 目标容器从起始到 end() 的全部元素。

同一行内用单个空格分隔，行末换行。对应区间为空时该行只输出换行。

样例

输入 #1

10
0 1 2 3 4 5 6 7 8 9
10
5 6 7 8 9 10 11 12 13 14

输出 #1

5 6 7 8 9
5 6 7 8 9 0 0 0 0 0

输入 #2

3
1 2 3
2
8 9

输出 #2

0 0

说明

\(0 \le n,m \le 1000\)，元素绝对值不超过 \(10^9\)。同一容器内元素互不相同。

样例 #1 容量取 \(10\)，交集只有 \(5\) 个，后五个是 resize 留下的 \(0\)。样例 #2 没有交集，第一行为空，第二行是两个补零。