codeforces-scrape

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

1227B.md (2403B)


      1 Source: https://codeforces.com/problemset/problem/1227/B
      2 
      3 B. Box
      4 
      5 time limit per test
      6 
      7 1 second
      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 Permutation $p$ is a sequence of integers $p=[p_1, p_2, \dots, p_n]$, consisting of $n$ distinct (unique) positive integers between $1$ and $n$, inclusive. For example, the following sequences are permutations: $[3, 4, 1, 2]$, $[1]$, $[1, 2]$. The following sequences are not permutations: $[0]$, $[1, 2, 1]$, $[2, 3]$, $[0, 1, 2]$.
     22 
     23 The important key is in the locked box that you need to open. To open the box you need to enter secret code. Secret code is a permutation $p$ of length $n$.
     24 
     25 You don't know this permutation, you only know the array $q$ of prefix maximums of this permutation. Formally:
     26 
     27 * $q_1=p_1$,
     28 * $q_2=\max(p_1, p_2)$,
     29 * $q_3=\max(p_1, p_2,p_3)$,
     30 * ...
     31 * $q_n=\max(p_1, p_2,\dots,p_n)$.
     32 
     33 You want to construct any possible suitable permutation (i.e. any such permutation, that calculated $q$ for this permutation is equal to the given array).
     34 
     35 Input
     36 
     37 The first line contains integer number $t$ ($1 \le t \le 10^4$) — the number of test cases in the input. Then $t$ test cases follow.
     38 
     39 The first line of a test case contains one integer $n$ $(1 \le n \le 10^{5})$ — the number of elements in the secret code permutation $p$.
     40 
     41 The second line of a test case contains $n$ integers $q_1, q_2, \dots, q_n$ $(1 \le q_i \le n)$ — elements of the array $q$ for secret permutation. It is guaranteed that $q_i \le q_{i+1}$ for all $i$ ($1 \le i \lt n$).
     42 
     43 The sum of all values $n$ over all the test cases in the input doesn't exceed $10^5$.
     44 
     45 Output
     46 
     47 For each test case, print:
     48 
     49 * If it's impossible to find such a permutation $p$, print "-1" (without quotes).
     50 * Otherwise, print $n$ distinct integers $p_1, p_2, \dots, p_n$ ($1 \le p_i \le n$). If there are multiple possible answers, you can print any of them.
     51 
     52 Example
     53 
     54 Input
     55 
     56 ```
     57 4
     58 5
     59 1 3 4 5 5
     60 4
     61 1 1 3 4
     62 2
     63 2 2
     64 1
     65 1
     66 ```
     67 
     68 Output
     69 
     70 ```
     71 1 3 4 5 2 
     72 -1
     73 2 1 
     74 1
     75 ```
     76 
     77 Note
     78 
     79 In the first test case of the example answer $[1,3,4,5,2]$ is the only possible answer:
     80 
     81 * $q_{1} = p_{1} = 1$;
     82 * $q_{2} = \max(p_{1}, p_{2}) = 3$;
     83 * $q_{3} = \max(p_{1}, p_{2}, p_{3}) = 4$;
     84 * $q_{4} = \max(p_{1}, p_{2}, p_{3}, p_{4}) = 5$;
     85 * $q_{5} = \max(p_{1}, p_{2}, p_{3}, p_{4}, p_{5}) = 5$.
     86 
     87 It can be proved that there are no answers for the second test case of the example.