A16622. Replace with Occurrences
编程题
普及/提高-
知识点
题目描述
给定一个长度为 $n$ 的序列 $b$，要求构造出另一个长度为 $n$ 的序列 $a$，使得对于新序列中每个元素 $a_i$，满足 $a_i$ 在 $a$ 中的出现次数恰好为 $b_i$。要求 $1 \le a_i \le n$。
输入格式
**本题有多组测试数据。**
第一行一个正整数 $T (1 \le T \le 10^4)$ 表示测试数据数量。
随后 $2T$ 行，第 $i + 1$ 至 $i + 2$ 行为第 $i$ 组测试数据。第 $i + 1$ 行一个整数 $n (1 \le n \le 2 \cdot 10 ^ 5)$，表示 $b$ 的长度，第二行 $n$ 个整数 $b_i (1 \le b_i \le n)$，表示 $b$ 序列。
第一行一个正整数 $T (1 \le T \le 10^4)$ 表示测试数据数量。
随后 $2T$ 行，第 $i + 1$ 至 $i + 2$ 行为第 $i$ 组测试数据。第 $i + 1$ 行一个整数 $n (1 \le n \le 2 \cdot 10 ^ 5)$，表示 $b$ 的长度，第二行 $n$ 个整数 $b_i (1 \le b_i \le n)$，表示 $b$ 序列。
输出格式
输出答案。若有多个答案，输出任意一个均可。如果不存在答案，输出
-1。输入输出样例
输入 #1
3 4 1 2 3 4 6 1 2 2 3 3 3 6 6 6 6 6 6 6
输出 #1
-1 4 5 5 6 6 6 2 2 2 2 2 2
说明/提示
在第一组测试数据中，没有一个数组 $a$ 符合要求。
在第二组测试数据中， $4, 5, 6$ 分别出现了 $1, 2, 3$ 次，所以 $a = \{ 4, 5, 5, 6, 6, 6 \}$ 符合要求。
在第二组测试数据中， $4, 5, 6$ 分别出现了 $1, 2, 3$ 次，所以 $a = \{ 4, 5, 5, 6, 6, 6 \}$ 符合要求。