codeforces-scrape

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

2046B.md (1611B)


      1 Source: https://codeforces.com/problemset/problem/2046/B
      2 
      3 B. Move Back at a Cost
      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 You are given an array of integers $a$ of length $n$. You can perform the following operation zero or more times:
     22 
     23 * In one operation choose an index $i$ ($1 \le i \le n$), assign $a_i := a_i + 1$, and then move $a_i$ to the back of the array (to the rightmost position). For example, if $a = [3, 5, 1, 9]$, and you choose $i = 2$, the array becomes $[3, 1, 9, 6]$.
     24 
     25 Find the lexicographically smallest$^{\text{∗}}$ array you can get by performing these operations.
     26 
     27 $^{\text{∗}}$An array $c$ is lexicographically smaller than an array $d$ if and only if one of the following holds:
     28 
     29 * $c$ is a prefix of $d$, but $c \ne d$; or
     30 * in the first position where $c$ and $d$ differ, the array $c$ has a smaller element than the corresponding element in $d$.
     31 
     32 Input
     33 
     34 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.
     35 
     36 The first line contains a single integer $n$ ($1 \le n \le 10^5$), the length of the array.
     37 
     38 The second line contains $n$ integers $a_1, a_2, \ldots, a_n$ ($1 \le a_i \le 10^9$), the elements of the array.
     39 
     40 It is guaranteed that the sum of $n$ over all test cases does not exceed $10^5$.
     41 
     42 Output
     43 
     44 For each test case, print the lexicographically smallest array you can get.
     45 
     46 Example
     47 
     48 Input
     49 
     50 ```
     51 3
     52 
     53 3
     54 
     55 2 1 3
     56 
     57 5
     58 
     59 1 2 2 1 4
     60 
     61 6
     62 
     63 1 2 3 6 5 4
     64 ```
     65 
     66 Output
     67 
     68 ```
     69 1 3 3 
     70 1 1 3 3 5 
     71 1 2 3 4 6 7
     72 ```