1006. F. Median Shuffle

题目描述

• 本题开启 Special Judge

给定一个奇数 $n$。存在一个长度为 $n$ 的排列 $a$。

令：

$$m=\frac{n+1}{2}.$$

构造一个长度为 $m$ 的序列 $b$。对于每个 $1\le i\le m$，定义：

$$b_i=\operatorname{median}{\char"28}a_1,a_2,\ldots,a_{2i-1}{\char"29}.$$

其中，$\operatorname{median}$ 为取中位数操作，长度为 $2i-1$ 的序列的中位数是将其从小到大排序后的第 $i$ 个元素。

将序列 $a$ 和序列 $b$ 拼接，再将得到的序列任意打乱，得到一个长度为：

$$n+m=\frac{3n+1}{2}$$

的序列 $c$。

现在给定 $n$ 和打乱后的序列 $c$，请构造任意一个可能的排列 $a$。如果不存在满足条件的排列，输出 -1。

序列 $c$ 中元素的顺序不包含任何额外信息。

样例解释

样例中，排列可以取为 ([2,1,3])。长度为 (1) 和 (3) 的奇数 前缀中位数均为 (2)，因此 (a) 与中位数序列拼接后的多重集合恰好 等于输入的多重集合。

样例输出不是唯一的。

数据范围

• (1\le T\le10)；
• (1\le n\le3\times10^5)，且 (n) 为奇数；
• (1\le c_i\le n)；
• 所有测试数据的 (n) 之和不超过 (6\times10^5)。

输入格式

输入包含多组测试数据。第一行包含一个整数 $T$（$1\le T\le 10$），表示测试数据组数。

对于每组测试数据：

第一行包含一个奇数 $n$（$1\le n\le 3\times 10^5$）。

第二行包含 $\frac{3n+1}{2}$ 个整数 $c_1,c_2,\ldots,c_{\frac{3n+1}{2}}$（$1\le c_i\le n$）。

输出格式

对于每组测试数据：

• 如果不存在满足条件的排列，输出一行 -1；
• 否则，输出一行 $n$ 个整数 $a_1,a_2,\ldots,a_n$，表示任意一个满足条件的排列。

如果存在多组合法答案，输出任意一组即可。

样例输入

1
3
2 1 2 3 2

样例输出

2 1 3

来源：2026杭电多校-测试专用（成都七中） 原题链接：http://acm.hdu.edu.cn/contest/problem_show.php?cid=1232&pid=1006 ⚠ 本题为 Special Judge。官方数据中的 .out 多为评测机判定输出（如 AC/OK/Correct/yes），导入后需自行提供 checker 方可正确评测。