codeforces-scrape

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

1942B.md (2068B)


      1 Source: https://codeforces.com/problemset/problem/1942/B
      2 
      3 B. Bessie and MEX
      4 
      5 time limit per test
      6 
      7 1.5 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 [MOOO! - Doja Cat](https://soundcloud.com/amalaofficial/mooo)
     22 
     23 ⠀
     24 
     25 Farmer John has a permutation $p_1, p_2, \ldots, p_n$, where every integer from $0$ to $n-1$ occurs exactly once. He gives Bessie an array $a$ of length $n$ and challenges her to construct $p$ based on $a$.
     26 
     27 The array $a$ is constructed so that $a_i$ = $\texttt{MEX}(p_1, p_2, \ldots, p_i) - p_i$, where the $\texttt{MEX}$ of an array is the minimum non-negative integer that does not appear in that array. For example, $\texttt{MEX}(1, 2, 3) = 0$ and $\texttt{MEX}(3, 1, 0) = 2$.
     28 
     29 Help Bessie construct any valid permutation $p$ that satisfies $a$. The input is given in such a way that at least one valid $p$ exists. If there are multiple possible $p$, it is enough to print one of them.
     30 
     31 Input
     32 
     33 The first line contains $t$ ($1 \leq t \leq 10^4$) — the number of test cases.
     34 
     35 The first line of each test case contains an integer $n$ ($1 \leq n \leq 2 \cdot 10^5$) — the lengths of $p$ and $a$.
     36 
     37 The second line of each test case contains $n$ integers $a_1, a_2, \ldots, a_n$ ($-n \leq a_i \leq n$) — the elements of array $a$.
     38 
     39 It is guaranteed that there is at least one valid $p$ for the given data.
     40 
     41 It is guaranteed that the sum of $n$ over all test cases does not exceed $2 \cdot 10^5$.
     42 
     43 Output
     44 
     45 For each test case, output $n$ integers on a new line, the elements of $p$.
     46 
     47 If there are multiple solutions, print any of them.
     48 
     49 Example
     50 
     51 Input
     52 
     53 ```
     54 3
     55 
     56 5
     57 
     58 1 1 -2 1 2
     59 
     60 5
     61 
     62 1 1 1 1 1
     63 
     64 3
     65 
     66 -2 1 2
     67 ```
     68 
     69 Output
     70 
     71 ```
     72 0 1 4 2 3 
     73 0 1 2 3 4 
     74 2 0 1
     75 ```
     76 
     77 Note
     78 
     79 In the first case, $p = [0, 1, 4, 2, 3]$ is one possible output.
     80 
     81 $a$ will then be calculated as $a_1 = \texttt{MEX}(0) - 0 = 1$, $a_2 = \texttt{MEX}(0, 1) - 1 = 1$, $a_3 = \texttt{MEX}(0, 1, 4) - 4 = -2$, $a_4 = \texttt{MEX}(0, 1, 4, 2) - 2 = 1$, $a_5 = \texttt{MEX}(0, 1, 4, 2, 3) - 3 = 2$.
     82 
     83 So, as required, $a$ will be $[1, 1, -2, 1, 2]$.