Time Limit: 2 sec / Memory Limit: 256 MB
配点 : 700 点
問題文
1,2,...,N を並べ替えてできる列であって、以下の条件を満たすものがあるかどうか判定し、あればその例をひとつ構成してください。
- 最長増加部分列の長さは A である
- 最長減少部分列の長さは B である
注釈
列 P の部分列とは P の要素をいくつか抜き出して元の順に並べてできる列のことを指し、 また、列 P の最長増加部分列とは、P の単調増加な部分列の中で列の長さが最大のものを指します。
同様に、列 P の最長減少部分列とは、P の単調減少な部分列の中で列の長さが最大のものを指します。
制約
- 1 \leq N,A,B \leq 3\times 10^5
- 入力はすべて整数である
入力
入力は以下の形式で標準入力から与えられる。
N A B
出力
条件を満たす列が存在しない場合、-1
を出力せよ。
そうでない場合、整数を N 個出力せよ。 i 個目には、構成した列の i 番目の要素を出力せよ。
入力例 1
5 3 2
出力例 1
2 4 1 5 3
{2,4,5} が最長増加部分列の一例、{4,3} が最長減少部分列の一例です。
入力例 2
7 7 1
出力例 2
1 2 3 4 5 6 7
入力例 3
300000 300000 300000
出力例 3
-1
Score : 700 points
Problem Statement
Determine if there exists a sequence obtained by permuting 1,2,...,N that satisfies the following conditions:
- The length of its longest increasing subsequence is A.
- The length of its longest decreasing subsequence is B.
If it exists, construct one such sequence.
Notes
A subsequence of a sequence P is a sequence that can be obtained by extracting some of the elements in P without changing the order.
A longest increasing subsequence of a sequence P is a sequence with the maximum length among the subsequences of P that are monotonically increasing.
Similarly, a longest decreasing subsequence of a sequence P is a sequence with the maximum length among the subsequences of P that are monotonically decreasing.
Constraints
- 1 \leq N,A,B \leq 3\times 10^5
- All input values are integers.
Input
Input is given from Standard Input in the following format:
N A B
Output
If there are no sequences that satisfy the conditions, print -1
.
Otherwise, print N integers. The i-th integer should be the i-th element of the sequence that you constructed.
Sample Input 1
5 3 2
Sample Output 1
2 4 1 5 3
One longest increasing subsequence of this sequence is {2,4,5}, and one longest decreasing subsequence of it is {4,3}.
Sample Input 2
7 7 1
Sample Output 2
1 2 3 4 5 6 7
Sample Input 3
300000 300000 300000
Sample Output 3
-1