← 返回题目列表

Codeforces · 2023/A

A. 数组串联

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

给你 $$$n$$$ 数组 $$$a_1$$$、$$$\ldots$$$、$$$a_n$$$。每个数组的长度是二。因此,$$$a_i = [a_{i, 1}, a_{i, 2}]$$$。您需要将数组连接成长度为 $$$2n$$$ 的单个数组,以使结果数组中的反转次数 $$$^{\dagger}$$$ 最小化。请注意,您不需要计算实际的反转次数。

更正式地说,您需要选择长度为 $$$n$$$ 的排列$$$^{\ddagger}$$$ $$$p$$$,以便数组 $$$b = [a_{p_1,1}, a_{p_1,2}, a_{p_2, 1}, a_{p_2, 2}, \ldots, a_{p_n,1}, a_{p_n,2}]$$$ 包含尽可能少的反转。

$$$^{\dagger}$$$数组 $$$c$$$ 中的反转数是索引 $$$i$$$ 和 $$$j$$$ 的对数,使得 $$$i < j$$$ 且 $$$c_i > c_j$$$。

$$$^{\ddagger}$$$长度$$$n$$$的排列是一个由从$$$1$$$到$$$n$$$以任意顺序的$$$n$$$不同整数组成的数组。例如,$$$[2,3,1,5,4]$$$是一个排列,但$$$[1,2,2]$$$不是排列($$$2$$$在数组中出现两次),$$$[1,3,4]$$$也不是排列($$$n=3$$$但数组中有$$$4$$$)。

输入

每个测试由多个测试用例组成。第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 10^4$$$) — 测试用例的数量。测试用例的描述如下。

每个测试用例的第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 10^5$$$) — 数组的数量。

以下 $$$n$$$ 行中的每一行都包含两个整数 $$$a_{i,1}$$$ 和 $$$a_{i,2}$$$ ($$$1 \le a_{i,j} \le 10^9$$$) — 第 $$$i$$$ 数组的元素。

保证所有测试用例的$$$n$$$总和不超过$$$10^5$$$。

输出

对于每个测试用例,输出 $$$2n$$$ 整数 - 您获得的数组的元素。如果有多个解,输出任意一个。

示例

输入 #1

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

输出 #1

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

注意

在第一个测试用例中,我们按照 $$$2, 1$$$ 的顺序连接数组。让我们考虑一下结果数组 $$$b = [2, 3, 1, 4]$$$ 中的反转:

- $$$i = 1$$$,$$$j = 3$$$,因为 $$$b_1 = 2 > 1 = b_3$$$;
- $$$i = 2$$$,$$$j = 3$$$,因为 $$$b_2 = 3 > 1 = b_3$$$。

因此,反转次数为 $$$2$$$。可以证明这是最小可能的反转次数。

在第二个测试用例中,我们按照 $$$3, 1, 2$$$ 的顺序连接数组。让我们考虑一下结果数组 $$$b = [2, 1, 3, 2, 4, 3]$$$ 中的反转:

- $$$i = 1$$$,$$$j = 2$$$,因为 $$$b_1 = 2 > 1 = b_2$$$;
- $$$i = 3$$$,$$$j = 4$$$,因为 $$$b_3 = 3 > 2 = b_4$$$;
- $$$i = 5$$$,$$$j = 6$$$,因为 $$$b_5 = 4 > 3 = b_6$$$。

因此,反转次数为 $$$3$$$。可以证明这是最小可能的反转次数。

在第三个测试用例中,我们按照 $$$4, 2, 1, 5, 3$$$ 的顺序连接数组。