codeforces-scrape

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

2044D.md (1978B)


      1 Source: https://codeforces.com/problemset/problem/2044/D
      2 
      3 D. Harder Problem
      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 a sequence of positive integers, a positive integer is called a mode of the sequence if it occurs the maximum number of times that any positive integer occurs. For example, the mode of $[2,2,3]$ is $2$. Any of $9$, $8$, or $7$ can be considered to be a mode of the sequence $[9,9,8,8,7,7]$.
     22 
     23 You gave UFO an array $a$ of length $n$. To thank you, UFO decides to construct another array $b$ of length $n$ such that $a_i$ is a mode of the sequence $[b_1, b_2, \ldots, b_i]$ for all $1 \leq i \leq n$.
     24 
     25 However, UFO doesn't know how to construct array $b$, so you must help her. Note that $1 \leq b_i \leq n$ must hold for your array for all $1 \leq i \leq n$.
     26 
     27 Input
     28 
     29 The first line contains $t$ ($1 \leq t \leq 10^4$) — the number of test cases.
     30 
     31 The first line of each test case contains an integer $n$ ($1 \leq n \leq 2 \cdot 10^5$) — the length of $a$.
     32 
     33 The following line of each test case contains $n$ integers $a_1, a_2, \ldots, a_n$ ($1 \leq a_i \leq n$).
     34 
     35 It is guaranteed that the sum of $n$ over all test cases does not exceed $2 \cdot 10^5$.
     36 
     37 Output
     38 
     39 For each test case, output $n$ numbers $b_1, b_2, \ldots, b_n$ ($1 \leq b_i \leq n$) on a new line. It can be shown that $b$ can always be constructed. If there are multiple possible arrays, you may print any.
     40 
     41 Example
     42 
     43 Input
     44 
     45 ```
     46 4
     47 
     48 2
     49 
     50 1 2
     51 
     52 4
     53 
     54 1 1 1 2
     55 
     56 8
     57 
     58 4 5 5 5 1 1 2 1
     59 
     60 10
     61 
     62 1 1 2 2 1 1 3 3 1 1
     63 ```
     64 
     65 Output
     66 
     67 ```
     68 1 2
     69 1 1 2 2
     70 4 5 5 1 1 2 2 3
     71 1 8 2 2 1 3 3 9 1 1
     72 ```
     73 
     74 Note
     75 
     76 Let's verify the correctness for our sample output in test case $2$.
     77 
     78 * At $i = 1$, $1$ is the only possible mode of $[1]$.
     79 * At $i = 2$, $1$ is the only possible mode of $[1, 1]$.
     80 * At $i = 3$, $1$ is the only possible mode of $[1, 1, 2]$.
     81 * At $i = 4$, $1$ or $2$ are both modes of $[1, 1, 2, 2]$. Since $a_i = 2$, this array is valid.