远端评测题 3000ms 512MiB

中性的色调(※※)

该比赛已结束,您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

给定两个序列 a,ba,b,将 bb 中所有元素以任意顺序在任意位置插入 aa 中,使得形成的新序列 cc 的最长上升子序列最短,输出你的序列 cc

输入描述

每个测试包含多个测试用例。第一行包含一个整数 tt (1t104)(1 \leq t \leq 10^4) - 测试用例数。 (1t104)(1 \leq t \leq 10^4) - 测试用例的数量。测试用例说明如下。

每个测试用例的第一行包含两个整数 n,mn, m $(1 \leq n \leq 2 \cdot 10^5, 1 \leq m \leq 2 \cdot 10^5)$ - 数组 aa 的长度和数组 aa 的长度。 $(1 \leq n \leq 2 \cdot 10^5, 1 \leq m \leq 2 \cdot 10^5)$ -数组 aa 的长度和数组 bb 的长度。

每个测试用例的第二行包含 nn 个整数 a1,a2,,ana_1, a_2, \ldots, a_n (1ai109)(1 \leq a_i \leq 10^9) - 数组 a1,a2,,ana_1, a_2, \ldots, a_n 的元素。 (1ai109)(1 \leq a_i \leq 10^9) -数组 aa 的元素。

每个测试用例的第三行包含 mm 个整数 b1,b2,,bmb_1, b_2, \ldots, b_m(1bi109)(1 \leq b_i \leq 10^9) - 数组 bb 的元素。

保证所有测试用例的 nn 之和不超过 21052\cdot 10^5 ,所有测试用例的 mm 之和不超过 21052\cdot 10^5

输出描述

对于每个测试用例,输出 n+mn + m 个数字--插入后得到的最终数组 c1,c2,,cn+mc_1, c_2, \ldots, c_{n+m} 中的元素,使得 LIS(c)\text{LIS}(c) 的值最小。如果有多个答案,可以输出任意一个。

7
2 1
6 4
5
5 5
1 7 2 4 5
5 4 1 2 7
1 9
7
1 2 3 4 5 6 7 8 9
3 2
1 3 5
2 4
10 5
1 9 2 3 8 1 4 7 2 9
7 8 5 4 6
2 1
2 2
1
6 1
1 1 1 1 1 1
777
6 5 4
1 1 7 7 2 2 4 4 5 5
9 8 7 7 6 5 4 3 2 1
1 3 5 2 4
1 9 2 3 8 8 1 4 4 7 7 2 9 6 5
2 2 1
777 1 1 1 1 1 1

说明

在第一个测试用例 LIS(a)=LIS([6,4])=1\text{LIS}(a) = \text{LIS}([6, 4]) = 1 中。我们可以在 6644 之间插入数字 55 ,然后是 LIS(c)=LIS([6,5,4])=1\text{LIS}(c) = \text{LIS}([6, 5, 4]) = 1

在第二个测试用例中, $\text{LIS}([\underline{1}, 7, \underline{2}, \underline{4}, \underline{5}])$ = 44 。插入后为 c=[1,1,7,7,2,2,4,4,5,5]c = [1, 1, 7, 7, 2, 2, 4, 4, 5, 5] 。不难看出, LIS(c)=4\text{LIS}(c) = 4 .由此可见, LIS(c)\text{LIS}(c) 不可能小于 44

12.03上午8点半练习及作业

未认领
状态
已结束
题目
11
开始时间
2023-12-3 8:30
截止时间
2023-12-8 23:59
可延期
24 小时