codeforces-scrape

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

1506E.md (2690B)


      1 Source: https://codeforces.com/problemset/problem/1506/E
      2 
      3 E. Restoring the Permutation
      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 A permutation is a sequence of $n$ integers from $1$ to $n$, in which all numbers occur exactly once. For example, $[1]$, $[3, 5, 2, 1, 4]$, $[1, 3, 2]$ are permutations, and $[2, 3, 2]$, $[4, 3, 1]$, $[0]$ are not.
     22 
     23 Polycarp was presented with a permutation $p$ of numbers from $1$ to $n$. However, when Polycarp came home, he noticed that in his pocket, the permutation $p$ had turned into an array $q$ according to the following rule:
     24 
     25 * $q_i = \max(p_1, p_2, \ldots, p_i)$.
     26 
     27 Now Polycarp wondered what lexicographically minimal and lexicographically maximal permutations could be presented to him.
     28 
     29 An array $a$ of length $n$ is lexicographically smaller than an array $b$ of length $n$ if there is an index $i$ ($1 \le i \le n$) such that the first $i-1$ elements of arrays $a$ and $b$ are the same, and the $i$-th element of the array $a$ is less than the $i$-th element of the array $b$. For example, the array $a=[1, 3, 2, 3]$ is lexicographically smaller than the array $b=[1, 3, 4, 2]$.
     30 
     31 For example, if $n=7$ and $p=[3, 2, 4, 1, 7, 5, 6]$, then $q=[3, 3, 4, 4, 7, 7, 7]$ and the following permutations could have been as $p$ initially:
     32 
     33 * $[3, 1, 4, 2, 7, 5, 6]$ (lexicographically minimal permutation);
     34 * $[3, 1, 4, 2, 7, 6, 5]$;
     35 * $[3, 2, 4, 1, 7, 5, 6]$;
     36 * $[3, 2, 4, 1, 7, 6, 5]$ (lexicographically maximum permutation).
     37 
     38 For a given array $q$, find the lexicographically minimal and lexicographically maximal permutations that could have been originally presented to Polycarp.
     39 
     40 Input
     41 
     42 The first line contains one integer $t$ ($1 \le t \le 10^4$). Then $t$ test cases follow.
     43 
     44 The first line of each test case contains one integer $n$ ($1 \le n \le 2 \cdot 10^5$).
     45 
     46 The second line of each test case contains $n$ integers $q_1, q_2, \ldots, q_n$ ($1 \le q_i \le n$).
     47 
     48 It is guaranteed that the array $q$ was obtained by applying the rule from the statement to some permutation $p$.
     49 
     50 It is guaranteed that the sum of $n$ over all test cases does not exceed $2 \cdot 10^5$.
     51 
     52 Output
     53 
     54 For each test case, output two lines:
     55 
     56 * on the first line output $n$ integers — lexicographically minimal permutation that could have been originally presented to Polycarp;
     57 * on the second line print $n$ integers — lexicographically maximal permutation that could have been originally presented to Polycarp;
     58 
     59 Example
     60 
     61 Input
     62 
     63 ```
     64 4
     65 7
     66 3 3 4 4 7 7 7
     67 4
     68 1 2 3 4
     69 7
     70 3 4 5 5 5 7 7
     71 1
     72 1
     73 ```
     74 
     75 Output
     76 
     77 ```
     78 3 1 4 2 7 5 6 
     79 3 2 4 1 7 6 5 
     80 1 2 3 4 
     81 1 2 3 4 
     82 3 4 5 1 2 7 6 
     83 3 4 5 2 1 7 6 
     84 1 
     85 1
     86 ```