#1883. Two permutations

    ID: 1883 传统题 1000ms 256MiB 尝试: 0 已通过: 0 难度: NOI/NOI+/CTS 上传者: 标签>CTT赛事:contest1857来源:qoj.ac数据:公开样例贪心

Two permutations

Two permutations

题目描述

标题: Two permutations - Problem - QOJ.ac

#9641. Two permutations

Statistics

The problem was used in the following contests:

题目描述

小 D 有一个长度为 2n 的序列 a1,a2,a3,…,a2n,其中 1∼n 的每一个数在这个序列中都恰好出现了两次。并且 a1,a2,a3,…,an 构成了一个 1∼n 的排列。

小 D 记数字 i 的两个出现位置为 xi,yi 满足 1≤xi≤n<yi≤2n。

小 D 还定义了一个集合运算 ⊕ 如下。

A⊕B={x∣[x∈A]+[x∈B]=1}

定义 f(S) 表示的是 S 中最小没有出现过的正整数。

现在小 D 会告诉你 vi=f({axi}⊕{axi+1}⊕⋯⊕{ayi})。他希望你根据序列 v 构造一个序列 a 使其符合条件。

输入格式

第一行为一个正整数 T,表示数据组数。

接下来 2T 行,描述 T 组数据。

每组数据的第一行为一个正整数 n,表示序列中出现的数字数量。

每组数据的第二行为 n 个正整数 v1,v2,v3,…,vn,表示求出来的值。

输出格式

对于所有的 T 组数据输出答案。

每组数据的第一行为一个字符串 Yes 或者是 No,表示是否有解。

如果有解那么在第二行输出 2n 个正整数 a1,a2,a3,…,a2n,表示你构造出的序列,如果存在多组符合条件的构造随便给出一组即可。

样例

样例输入
2
4
1 2 2 2
3
3 2 1
样例输出
Yes
3 2 4 1 4 2 3 1
No

数据范围

子任务编号 n≤ ∑n≤ 特殊性质 分数 1 5 50 10 2 10 100 10 3 2×105 2×106 A 15 4 2×105 2×106 B 15 5 2×105 2×106 50

特殊性质 A:满足 vi≤4。

特殊性质 B:满足 vvi=vi。

对于 100% 的数据,满足 1≤T≤10,1≤n≤2×105,1≤∑n≤2×106,1≤vi≤n。

下发文件的答案文件中并不存在构造方案。

输入格式

(见题面原文)

输出格式

(见题面原文)

数据范围

(见题面原文)

样例

样例 1

2
4
1 2 2 2
3
3 2 1
Yes
No

样例 2

1
10
1 2 1 1 3 3 4 2 3 4
Yes