luogu#P10033. 「Cfz Round 3」Sum of Permutation

    ID: 13994 远端评测题 500ms 512MiB 尝试: 0 已通过: 0 难度: 4 上传者: 标签>数学洛谷原创Special JudgeO2优化构造洛谷月赛Ad-hoc

「Cfz Round 3」Sum of Permutation

题目描述

请注意本题特殊的时间限制。

给定一个 1n1\sim n 的排列 pp

你需要构造一个长度为 nn 的序列 aa,满足:

  • 序列 aa 中的每个元素均为不大于 nn 的正整数;
  • 不存在有序整数二元组 (l,r)(l,r),满足 1lrn1 \le l \le r \le ni=lrai=i=lrpi\sum\limits_{i=l}^r a_i=\sum\limits_{i=l}^r p_i

或报告无解。

其中,1n1\sim n 的排列指满足所有不大于 nn 的正整数恰好出现一次的序列。

输入格式

本题有多组测试数据。

第一行输入一个整数 TT,表示测试数据组数。

接下来依次输入每组测试数据。对于每组测试数据:

  • 第一行输入一个整数 nn
  • 第二行输入 nn 个整数,表示给定的排列 pp

输出格式

对于每组数据,输出一行:

  • 若存在满足条件的序列 aa,则输出用空格分隔的 nn 个整数,表示你构造的序列 aa
  • 若不存在满足条件的序列 aa,则输出 1-1

所有满足要求的输出均可通过。

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」

对于第 11 组数据,{1,3,3}\{1,3,3\}{1,1,3}\{1,1,3\} 均为满足条件的序列 aa

对于第 22 组数据,可以证明不存在满足条件的序列 aa

对于第 33 组数据,除 {5,3,2,1,1}\{5,3,2,1,1 \} 外,{3,4,5,3,2}\{3,4,5,3,2 \}{1,4,5,3,4}\{1,4,5,3,4 \}{5,3,3,4,5}\{5,3,3,4,5\} 等均为满足条件的序列 aa

「数据范围」

n\sum n 表示单个测试点中 nn 的和。

对于所有数据,1T50001 \le T \le 50002n1062 \le n \le 10^6n106\sum n \le 10^6,保证 pp1n1\sim n 的排列。

只有你通过本题的所有测试点,你才能获得本题的分数。

本题输入输出量较大,请使用较快的输入输出方式。