2078B.md (2532B)
1 Source: https://codeforces.com/problemset/problem/2078/B 2 3 B. Vicious Labyrinth 4 5 time limit per test 6 7 1.5 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 [Axium Crisis - ak+q](https://youtu.be/1HyuI8Bvnsg?si=6amlU5OPKnJiydZs) 22 23 There are $n$ cells in a labyrinth, and cell $i$ ($1 \leq i \leq n$) is $n - i$ kilometers away from the exit. In particular, cell $n$ is the exit. Note also that each cell is connected to the exit but is not accessible from any other cell in any way. 24 25 In each cell, there is initially exactly one person stuck in it. You want to help everyone get as close to the exit as possible by installing a teleporter in each cell $i$ ($1 \leq i \leq n$), which translocates the person in that cell to another cell $a_i$. 26 27 The labyrinth owner caught you in the act. Amused, she let you continue, but under some conditions: 28 29 * Everyone must use the teleporter exactly $k$ times. 30 * No teleporter in any cell can lead to the same cell it is in. Formally, $i \neq a_i$ for all $1 \leq i \leq n$. 31 32 You must find a teleporter configuration that minimizes the sum of distances of all individuals from the exit after using the teleporter exactly $k$ times while still satisfying the restrictions of the labyrinth owner. 33 34 If there are many possible configurations, you can output any of them. 35 36 Input 37 38 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. 39 40 The first and only line of each test case contains two integers $n$ and $k$ ($2 \leq n \leq 2 \cdot 10^5$, $1 \leq k \leq 10^9$) — the number of cells in the labyrinth and the value $k$. 41 42 It is guaranteed that the total sum of $n$ across all test cases does not exceed $2 \cdot 10^5$. 43 44 Output 45 46 For each test case, output $n$ integers — the destinations of the teleporters $a_1, a_2, \ldots, a_n$ in order, satisfying the given conditions ($1 \leq a_i \leq n$, $a_i \neq i$). 47 48 Example 49 50 Input 51 52 ``` 53 2 54 55 2 1 56 57 3 2 58 ``` 59 60 Output 61 62 ``` 63 2 1 64 65 2 3 2 66 ``` 67 68 Note 69 70 In the first test case, the position of each person is as follows. 71 72 * Before teleporting: $[1, 2]$. 73 * First teleportation: $[2, 1]$. 74 75 The distance sum is $(2-2) + (2-1) = 1$, which is the minimum possible. 76 77 In the second test case, the position of each person is as follows. 78 79 * Before teleporting: $[1, 2, 3]$. 80 * First teleportation: $[2, 3, 2]$. 81 * Second teleportation: $[3, 2, 3]$. 82 83 The distance sum is $(3-3) + (3-2) + (3-3) = 1$, which is the minimum possible.