codeforces-scrape

Codeforces scraped problems and editorials
git clone git://git.laack.co/codeforces-scrape.git
Log | Files | Refs | README

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.