1770B.md (1845B)
1 Source: https://codeforces.com/problemset/problem/1770/B 2 3 B. Koxia and Permutation 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 Reve has two integers $n$ and $k$. 22 23 Let $p$ be a permutation$^\dagger$ of length $n$. Let $c$ be an array of length $n - k + 1$ such that $$c_i = \max(p_i, \dots, p_{i+k-1}) + \min(p_i, \dots, p_{i+k-1}).$$ Let the cost of the permutation $p$ be the maximum element of $c$. 24 25 Koxia wants you to construct a permutation with the minimum possible cost. 26 27 $^\dagger$ A permutation of length $n$ is an array consisting of $n$ distinct integers from $1$ to $n$ in arbitrary order. For example, $[2,3,1,5,4]$ is a permutation, but $[1,2,2]$ is not a permutation ($2$ appears twice in the array), and $[1,3,4]$ is also not a permutation ($n=3$ but there is $4$ in the array). 28 29 Input 30 31 Each test consists of multiple test cases. The first line contains a single integer $t$ ($1 \leq t \leq 2000$) — the number of test cases. The description of test cases follows. 32 33 The first line of each test case contains two integers $n$ and $k$ ($1 \leq k \leq n \leq 2 \cdot 10^5$). 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$ integers $p_1,p_2,\dots,p_n$, which is a permutation with minimal cost. If there is more than one permutation with minimal cost, you may output any of them. 40 41 Example 42 43 Input 44 45 ``` 46 3 47 48 5 3 49 50 5 1 51 52 6 6 53 ``` 54 55 Output 56 57 ``` 58 5 1 2 3 4 59 1 2 3 4 5 60 3 2 4 1 6 5 61 ``` 62 63 Note 64 65 In the first test case, 66 67 * $c_1 = \max(p_1,p_2,p_3) + \min(p_1,p_2,p_3) = 5 + 1 = 6$. 68 * $c_2 = \max(p_2,p_3,p_4) + \min(p_2,p_3,p_4) = 3 + 1 = 4$. 69 * $c_3 = \max(p_3,p_4,p_5) + \min(p_3,p_4,p_5) = 4 + 2 = 6$. 70 71 Therefore, the cost is $\max(6,4,6)=6$. It can be proven that this is the minimal cost.