1473C.md (2402B)
1 Source: https://codeforces.com/problemset/problem/1473/C 2 3 C. No More Inversions 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 have a sequence $a$ with $n$ elements $1, 2, 3, \dots, k - 1, k, k - 1, k - 2, \dots, k - (n - k)$ ($k \le n \lt 2k$). 22 23 Let's call as inversion in $a$ a pair of indices $i \lt j$ such that $a[i] \gt a[j]$. 24 25 Suppose, you have some permutation $p$ of size $k$ and you build a sequence $b$ of size $n$ in the following manner: $b[i] = p[a[i]]$. 26 27 Your goal is to find such permutation $p$ that the total number of inversions in $b$ doesn't exceed the total number of inversions in $a$, and $b$ is lexicographically maximum. 28 29 Small reminder: the sequence of $k$ integers is called a permutation if it contains all integers from $1$ to $k$ exactly once. 30 31 Another small reminder: a sequence $s$ is lexicographically smaller than another sequence $t$, if either $s$ is a prefix of $t$, or for the first $i$ such that $s_i \ne t_i$, $s_i \lt t_i$ holds (in the first position that these sequences are different, $s$ has smaller number than $t$). 32 33 Input 34 35 The first line contains a single integer $t$ ($1 \le t \le 1000$) — the number of test cases. 36 37 The first and only line of each test case contains two integers $n$ and $k$ ($k \le n \lt 2k$; $1 \le k \le 10^5$) — the length of the sequence $a$ and its maximum. 38 39 It's guaranteed that the total sum of $k$ over test cases doesn't exceed $10^5$. 40 41 Output 42 43 For each test case, print $k$ integers — the permutation $p$ which maximizes $b$ lexicographically without increasing the total number of inversions. 44 45 It can be proven that $p$ exists and is unique. 46 47 Example 48 49 Input 50 51 ``` 52 4 53 1 1 54 2 2 55 3 2 56 4 3 57 ``` 58 59 Output 60 61 ``` 62 1 63 1 2 64 2 1 65 1 3 2 66 ``` 67 68 Note 69 70 In the first test case, the sequence $a = [1]$, there is only one permutation $p = [1]$. 71 72 In the second test case, the sequence $a = [1, 2]$. There is no inversion in $a$, so there is only one permutation $p = [1, 2]$ which doesn't increase the number of inversions. 73 74 In the third test case, $a = [1, 2, 1]$ and has $1$ inversion. If we use $p = [2, 1]$, then $b = [p[a[1]], p[a[2]], p[a[3]]] = [2, 1, 2]$ and also has $1$ inversion. 75 76 In the fourth test case, $a = [1, 2, 3, 2]$, and since $p = [1, 3, 2]$ then $b = [1, 3, 2, 3]$. Both $a$ and $b$ have $1$ inversion and $b$ is the lexicographically maximum.