2167E.md (3055B)
1 Source: https://codeforces.com/problemset/problem/2167/E 2 3 E. khba Loves to Sleep! 4 5 time limit per test 6 7 3 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 khba has $n$ friends, each standing on a line at position $a_i$, and each of them is in the range $[0, x]$. 22 23 They all want to come to him. One of his friends, Isamatdin, gave him $k$ teleports. Each friend will walk to the nearest teleport (choosing the shortest distance). Once a friend reaches a teleport, khba and the friend can instantly meet. 24 25 But khba is so tired that he'll be sleeping while his friends are walking toward him. Now he wants to choose $k$ teleport positions so that their positions are distinct and lie within the range $[0, x]$, in order to maximize the time it takes for the first friend who reaches a teleport to reach it. Assume that friends move at the same speed. 26 27 Since khba isn't good at calculations, you should output the $k$ chosen teleport positions. 28 29 Input 30 31 Each test contains multiple test cases. The first line contains a single integer $t$ ($1 \leq t \leq 10^4$) — the number of test cases. The description of the test cases follows. 32 33 The first line of each test case contains three integers $n$, $k$, and $x$ ($1 \leq n, k \leq 2 \cdot 10^5$, $k - 1 \leq x \leq 10^9$) — the number of friends, the number of teleports, and the range of possible positions for the teleports. 34 35 The second line of each test case contains $n$ integers $a_1, a_2, \dots, a_n$ ($0 \leq a_i \leq x$) — the positions of khba's friends. 36 37 It is guaranteed that the sum of $n$ over all test cases does not exceed $2 \cdot 10^5$. 38 39 It is guaranteed that the sum of $k$ over all test cases does not exceed $2 \cdot 10^5$. 40 41 Output 42 43 For each test case, output a single line containing $k$ integers — the $k$ chosen teleport positions. The positions must be distinct and lie within the range $[0, x]$. The positions may be output in any order. 44 45 If there are multiple optimal choices, output any of them. 46 47 Example 48 49 Input 50 51 ``` 52 10 53 54 4 1 4 55 56 1 0 2 4 57 58 5 5 4 59 60 0 1 2 3 4 61 62 2 1 4 63 64 4 0 65 66 3 4 6 67 68 2 4 3 69 70 3 2 12 71 72 6 12 0 73 74 4 3 12 75 76 8 12 0 4 77 78 1 1 1000000000 79 80 0 81 82 1 1 1000000000 83 84 1000000000 85 86 3 4 9 87 88 8 7 9 89 90 3 4 9 91 92 2 0 1 93 ``` 94 95 Output 96 97 ``` 98 3 99 0 1 2 3 4 100 2 101 0 1 5 6 102 3 9 103 2 6 10 104 1000000000 105 0 106 0 1 2 3 107 6 7 8 9 108 ``` 109 110 Note 111 112 Sample 1. Friends at positions $[1,0,2,4]$. Chosen teleport position: $[3]$. 113 114 Nearest teleport for each friend is in $3$, minimal times for friends are $[2, 3, 1, 1]$, respectively. 115 116 Sample 2. Friends at positions $[0,1,2,3,4]$. Chosen teleport positions: $[0,1,2,3,4]$. 117 118 Minimal times for friends are $[0, 0, 0, 0, 0]$, respectively. 119 120 Sample 3. Friends at positions $[4,0]$. Chosen teleport position: $[2]$. 121 122 Minimal times for friends are $[2, 2]$, respectively. 123 124 Sample 4. Friends at positions $[2,4,3]$. Chosen teleport positions: $[0,1,5,6]$. 125 126 Minimal times for friends are $[1, 1, 2]$, respectively. 127 128 Sample 5. Friends at positions $[6,12,0]$. Chosen teleport positions: $[3,9]$. 129 130 Minimal times for friends are $[3, 3, 3]$, respectively.