codeforces-scrape

Codeforces scraped problems and editorials
git clone git://git.laack.co/codeforces-scrape.git
Log | Files | Refs | README

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.