二倍序列

题目描述:

称一个长度为 \( N \) 的序列 \( a = [a_1, a_2, \ldots, a_N] \) 为二倍序列，当且仅当以下两个条件均被满足：

1. \( N \) 是正偶数；
2. 对每个 \( i \)（\( 1 \le i \le \frac{N}{2} \)），有 \( a_i = a_{i + \frac{N}{2}} \)。

进一步地，定义函数 \( f(x) \) 为序列 \( x \) 中不同二倍子序列（即，是二倍序列的子序列）的数量。两个子序列被认为不同，当且仅当这两个子序列对应原序列的位置不完全相同。

小 Y 有一个长为 \( n \) 的序列 \( s \)。其希望找到一个长为 \( n \) 的序列 \( t \)，满足如下条件：

\[
f(t) = \lfloor [f(s)]^{1/4} \rfloor
\]

你的任务是找到一个符合条件的序列 \( t \)。可以证明这总是可能的。

输入格式:

输入的第一行格式如下：

\( \quad \begin{matrix} T \end{matrix} \)

接下来是 \( T \) 个测试数据，每个的格式如下：

\( \quad \begin{matrix} n \\ s_1 & s_2 & \cdots & s_n \end{matrix} \)

输出格式:

对每个测试数据，输出一行 \( n \) 个整数，代表你构造的序列 \( t \)。

样例输入:

3
4
1 1 2 1
5
1 2 3 4 5
6
1 1 1 1 1 1

样例输出:

1 1 2 3
1 2 3 4 5
1 3 2 3 4 1

提示:

样例解释 #1

1. \( f([1, 1, 2, 1]) = 3 \)，\( f([1, 1, 2, 3]) = 1 \)。
2. \( f([1, 2, 3, 4, 5]) = 0 \)。
3. \( f([1, 1, 1, 1, 1, 1]) = 31 \)，\( f([1, 3, 2, 3, 4, 1]) = 2 \)。

对于所有数据：

• \( 1 \le T \le 240 \)
• \( 2 \le n \le 120 \)
• \( 1 \le s_i \le n \)

子任务	分值	附加约束
\( \bf1 \)	\( 5 \)	\( T \le 40 \)；\( n \le 5 \)
\( \bf2 \)	\( 12 \)	\( T \le 40 \)；\( n \le 6 \)
\( \bf3 \)	\( 13 \)	\( T \le 40 \)；\( n \le 7 \)
\( \bf4 \)	\( 19 \)	\( T \le 40 \)；\( n \le 20 \)
\( \bf5 \)	\( 18 \)	\( T \le 40 \)；\( n \le 40 \)
\( \bf6 \)	\( 17 \)	\( n \le 80 \)
\( \bf7 \)	\( 16 \)	\( - \)

 

时间限制: 2000ms
空间限制: 512MB

---

来源: ItsMartlet_