P8397 [CCC 2022 S3] Good Samples

Note: the notes in the score are numbers. We define a subscore as a “non-empty contiguous sequence of notes”. That is, after sorting a sequence and removing duplicates, the difference between every two adjacent values is $1$. For example, $(3,4,2)$, $(1,2,3,4,2)$, and $(4)$ are subscores of $(1,2,3,4,2)$. Note that $(1,3)$ is not a subscore. If two subscores start or end at different positions in the piece, we call them “different subscores”. If all numbers at any two positions in a subscore are different, we call it a “good subscore”. The performers are very picky, and they require the following for the score: 1. All notes must be less than $m$. 2. There are $k$ good subscores in the score. They now ask you whether you can construct such a score.

The first line contains three integers $n, m, k$. Their meanings are described in the statement.

Output one line with $n$ integers, representing the score required by the performers. If there are one or more valid scores, output the lexicographically smallest one. If it is impossible to construct a score that satisfies the requirements, output `-1`.

For $20\%$ of the testdata: $1 \le n \le 16$, $m = 2$, $1 \le k \le 1000$. For another $20\%$ of the testdata: $1 \le n \le 10^6$, $m = 2$, $1 \le k \le 10^{18}$. For another $25\%$ of the testdata: $1 \le n \le 10^6$, $m = n$, $1 \le k \le 10^{18}$. For $100\%$ of the testdata: $1 \le n \le 10^6$, $1 \le m \le n$, $1 \le k \le 10^{18}$. Translated by ChatGPT 5