2137D.md (1513B)
1 Source: https://codeforces.com/problemset/problem/2137/D 2 3 D. Replace with Occurrences 4 5 time limit per test 6 7 2 seconds 8 9 memory limit per test 10 11 256 megabytes 12 13 input 14 15 standard input 16 17 output 18 19 standard output 20 21 Given an array $a$, let $f(x)$ be the number of occurrences of $x$ in the array $a$. For example, when $a=[1,2,3,1,4]$, then $f(1)=2$ and $f(3)=1$. 22 23 You have an array $b$ of size $n$. Please determine if there is an array $a$ of size $n$ such that $f(a_i)=b_i$ for all $1 \leq i \leq n$. If there is one, construct it. 24 25 Input 26 27 Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 10^4$). The description of the test cases follows. 28 29 The first line of each test case contains an integer $n$ ($1 \leq n \leq 2\cdot 10^5$). 30 31 The second line contains $n$ integers $b_1,b_2,\ldots,b_n$ ($1 \leq b_i \leq n$). 32 33 It is guaranteed that the sum of $n$ over all test cases does not exceed $2\cdot 10^5$. 34 35 Output 36 37 For each test case, output $-1$ if there is no valid array $a$. 38 39 Otherwise, print the array $a$ of $n$ integers on a new line. The elements should satisfy $1 \leq a_i \leq n$. 40 41 Example 42 43 Input 44 45 ``` 46 3 47 48 4 49 50 1 2 3 4 51 52 6 53 54 1 2 2 3 3 3 55 56 6 57 58 6 6 6 6 6 6 59 ``` 60 61 Output 62 63 ``` 64 -1 65 4 5 5 6 6 6 66 2 2 2 2 2 2 67 ``` 68 69 Note 70 71 In the first test case, it can be shown that no array matches the requirement. 72 73 In the second test case, $4$, $5$, $6$ appear $1,2,3$ times respectively. Thus, the output array is correct as $f(4),f(5),f(5),f(6),f(6),f(6)$ are $1,2,2,3,3,3$ respectively.