2084D.md (3090B)
1 Source: https://codeforces.com/problemset/problem/2084/D 2 3 D. Arcology On Permafrost 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 three integers $n$, $m$, and $k$, where $m \cdot k \lt n$. 22 23 For a sequence $b$ consisting of non-negative integers, define $f(b)$ as follows: 24 25 * You may perform the following operation on $b$: 26 + Let $l$ denote the current length of $b$. Choose a positive integer $1 \leq i \leq l - k + 1$, remove the subarray from index $i$ to $i + k - 1$ and concatenate the remaining parts. In other words, replace $b$ with $$[b_1, b_2, \ldots, b_{i - 1}, b_{i + k}, b_{i + k + 1}, \ldots, b_l].$$ 27 * $f(b)$ is defined as the minimum possible value of $\operatorname{mex}(b)$$^{\text{∗}}$ after performing the above operation at most $m$ times (possibly zero). 28 29 You need to construct a sequence $a$ of length $n$ consisting of non-negative integers, such that: 30 31 * For all $1 \le i \le n$, $0 \le a_i \le 10^9$. 32 * Over all such sequences $a$, $f(a)$ is maximized. 33 34 $^{\text{∗}}$The minimum excluded (MEX) of a collection of integers $c_1, c_2, \ldots, c_k$ is defined as the smallest non-negative integer $x$ which does not occur in the collection $c$. 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 line of each test case contains three integers $n$, $m$, and $k$ ($2 \le n \le 2 \cdot 10^5$, $1 \le m \lt n$, $1 \le k \lt n$, $1 \le m \cdot k \lt n$). 41 42 It is guaranteed that the sum of $n$ over all test cases does not exceed $2 \cdot 10^5$. 43 44 Output 45 46 For each test case, output $n$ integers $a_1, a_2, \ldots, a_n$ ($0 \le a_i \le 10^9$). 47 48 If there are multiple answers, print any of them. 49 50 Example 51 52 Input 53 54 ``` 55 8 56 57 2 1 1 58 59 5 2 2 60 61 6 1 4 62 63 8 2 2 64 65 8 1 5 66 67 11 3 3 68 69 22 6 3 70 71 17 2 2 72 ``` 73 74 Output 75 76 ``` 77 0 0 78 0 1 0 0 0 79 0 1 2 2 0 1 80 0 2 1 0 1 0 8 1 81 0 1 2 1000000000 1 0 1 2 82 1 0 0 1 0 2 1 0 2 1 0 83 0 2 1 0 2 1 0 3 2 1 0 2 1 0 2 1 0 2 1 0 2 1 84 4 0 2 1 3 4 0 2 1 0 3 4 0 1 2 1 3 85 ``` 86 87 Note 88 89 In the first test case, it can be shown that $f(a) = 1$, which is maximized. 90 91 In the second test case, it can be shown that $f(a) = 1$, which is maximized. $f(a) = 1$ since you can perform the following operations: 92 93 * Choose $i = 3$, remove the subarray from index $3$ to $4$ and concatenate the remaining parts. The sequence $a$ becomes $[0, 1, 0]$. 94 * Choose $i = 1$, remove the subarray from index $1$ to $2$ and concatenate the remaining parts. The sequence $a$ becomes $[0]$. 95 96 In the third test case, it can be shown that $f(a) = 2$, which is maximized. $f(a) = 2$ since you can perform the following operation: 97 98 * Choose $i = 2$, remove the subarray from index $2$ to $5$ and concatenate the remaining parts. The sequence $a$ becomes $[0, 1]$. 99 100 In the fourth test case, it can be shown that $f(a) = 2$, which is maximized. 101 102 In the fifth test case, it can be shown that $f(a) = 3$, which is maximized. 103 104 In the sixth test case, it can be shown that $f(a) = 2$, which is maximized.