luogu#P10033. 「Cfz Round 3」Sum of Permutation
「Cfz Round 3」Sum of Permutation
题目描述
请注意本题特殊的时间限制。
给定一个 的排列 。
你需要构造一个长度为 的序列 ,满足:
- 序列 中的每个元素均为不大于 的正整数;
- 不存在有序整数二元组 ,满足 且 ;
或报告无解。
其中, 的排列指满足所有不大于 的正整数恰好出现一次的序列。
输入格式
本题有多组测试数据。
第一行输入一个整数 ,表示测试数据组数。
接下来依次输入每组测试数据。对于每组测试数据:
- 第一行输入一个整数 。
- 第二行输入 个整数,表示给定的排列 。
输出格式
对于每组数据,输出一行:
- 若存在满足条件的序列 ,则输出用空格分隔的 个整数,表示你构造的序列 ;
- 若不存在满足条件的序列 ,则输出 。
所有满足要求的输出均可通过。
4
3
3 2 1
2
1 2
5
4 2 1 5 3
7
5 7 3 1 2 4 6
1 3 3
-1
5 3 2 1 1
2 3 5 4 6 3 1
提示
「样例解释 #1」
对于第 组数据, 和 均为满足条件的序列 。
对于第 组数据,可以证明不存在满足条件的序列 。
对于第 组数据,除 外,、、 等均为满足条件的序列 。
「数据范围」
设 表示单个测试点中 的和。
对于所有数据,,,,保证 是 的排列。
只有你通过本题的所有测试点,你才能获得本题的分数。
本题输入输出量较大,请使用较快的输入输出方式。