/ 
実行時間制限: 2 sec / メモリ制限: 1024 MiB
配点 : 1000 点
問題文
整数 N, L, R が与えられます。
これらの整数について、以下が成り立ちます。
- 2 \leq N
- 0\leq L < R \leq N
- (L, R)\neq (0, N)
長さ N の数列 A = (A_{0}, A_{1}, \dots , A_{N - 1}) を A = (0, 1, \dots, N - 1) と初期化します。
(R - L, R - L + 1, \dots , N - 1) の順列 P = (P_{0}, P_{1}, \dots, P_{N - (R - L) - 1}) をひとつ選び、i = 0, 1, \dots N - (R - L) - 1 の順に以下の操作を行います。
- P_{i} を |A| で割ったあまりを a とし、A_{a} を A から削除する(要素の削除後、数列 A の添え字は 0 から振り直されるものとする)
最終的に A = (L, L + 1, \dots , R - 1) となるような P が存在するか判定し、存在するならばそのような P をひとつ出力してください。
制約
- 2\leq N\leq 2\times 10^{5}
- 0\leq L < R\leq N
- (L, R) \neq (0, N)
- 入力は全て整数
入力
入力は以下の形式で標準入力から与えられます。
N L R
出力
A = (L, L + 1, \dots , R - 1) となるような P が存在しない場合は No と出力してください。
存在する場合は以下の形式で答えを出力してください。
Yes
P_{0} P_{1} \cdots P_{N - (R - L) - 1}
形式的には、1 行目に Yes を出力し、2 行目に P_{0}, P_{1}, \dots , P_{N - (R - L) - 1} を空白区切りで出力してください。
解が複数存在する場合はどれを出力しても正解とみなされます。
入力例 1
6 3 5
出力例 1
Yes 2 4 5 3
P = (2, 4, 5, 3) を選んだとき、A = (0, 1, 2, 3, 4, 5) から以下のように 4 回操作します。
-
P_{0} = 2 を |A| = 6 で割ったあまりは 2 なので、A_{2} = 2 を A から削除します。すると、A = (A_{0}, A_{1}, A_{2}, A_{3}, A_{4}) = (0, 1, 3, 4, 5) となります。
-
P_{1} = 4 を |A| = 5 で割ったあまりは 4 なので、A_{4} = 5 を A から削除します。すると、A = (A_{0}, A_{1}, A_{2}, A_{3}) = (0, 1, 3, 4) となります。
-
P_{2} = 5 を |A| = 4 で割ったあまりは 1 なので、A_{1} = 1 を A から削除します。すると、A = (A_{0}, A_{1}, A_{2}) = (0, 3, 4) となります。
-
P_{3} = 3 を |A| = 3 で割ったあまりは 0 なので、A_{0} = 0 を A から削除します。すると、A = (A_{0}, A_{1}) = (3, 4) となります。
よって、P = (2, 4, 5, 3) とすることで目標を達成できます。また、P = (5, 2, 4, 3) を出力しても良いです。
入力例 2
9 2 4
出力例 2
Yes 4 5 6 7 3 8 2
入力例 3
178 68 167
出力例 3
No
Score : 1000 points
Problem Statement
You are given integers N, L, R.
These integers satisfy the following:
- 2 \leq N
- 0\leq L < R \leq N
- (L, R)\neq (0, N)
Initialize a length-N sequence A = (A_{0}, A_{1}, \dots , A_{N - 1}) as A = (0, 1, \dots, N - 1).
Choose a permutation P = (P_{0}, P_{1}, \dots, P_{N - (R - L) - 1}) of (R - L, R - L + 1, \dots , N - 1), and perform the following operation for i = 0, 1, \dots N - (R - L) - 1 in this order.
- Let a be the remainder when P_{i} is divided by |A|, and remove A_{a} from A (after removing an element, the indices of sequence A are renumbered starting from 0).
Determine whether there exists a P such that A = (L, L + 1, \dots , R - 1) in the end, and if it exists, output one such P.
Constraints
- 2\leq N\leq 2\times 10^{5}
- 0\leq L < R\leq N
- (L, R) \neq (0, N)
- All input values are integers.
Input
The input is given from Standard Input in the following format:
N L R
Output
If there is no P that makes A = (L, L + 1, \dots , R - 1), output No.
If it exists, output a solution in the following format:
Yes
P_{0} P_{1} \cdots P_{N - (R - L) - 1}
Formally, output Yes on the first line, and output P_{0}, P_{1}, \dots , P_{N - (R - L) - 1} separated by spaces on the second line.
If there are multiple solutions, any of them will be considered correct.
Sample Input 1
6 3 5
Sample Output 1
Yes 2 4 5 3
When choosing P = (2, 4, 5, 3), perform four operations on A = (0, 1, 2, 3, 4, 5) as follows.
-
The remainder when P_{0} = 2 is divided by |A| = 6 is 2, so remove A_{2} = 2 from A. Then, A = (A_{0}, A_{1}, A_{2}, A_{3}, A_{4}) = (0, 1, 3, 4, 5).
-
The remainder when P_{1} = 4 is divided by |A| = 5 is 4, so remove A_{4} = 5 from A. Then, A = (A_{0}, A_{1}, A_{2}, A_{3}) = (0, 1, 3, 4).
-
The remainder when P_{2} = 5 is divided by |A| = 4 is 1, so remove A_{1} = 1 from A. Then, A = (A_{0}, A_{1}, A_{2}) = (0, 3, 4).
-
The remainder when P_{3} = 3 is divided by |A| = 3 is 0, so remove A_{0} = 0 from A. Then, A = (A_{0}, A_{1}) = (3, 4).
Therefore, the goal can be achieved by setting P = (2, 4, 5, 3). It is also acceptable to output P = (5, 2, 4, 3).
Sample Input 2
9 2 4
Sample Output 2
Yes 4 5 6 7 3 8 2
Sample Input 3
178 68 167
Sample Output 3
No