/ 
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 1100 点
問題文
整数列 A=(A_1, A_2, \ldots, A_{N + K-1}) (1 \leq A_i \leq N+K-1) に対して、B_i を A_i,A_{i+1},\ldots,A_{i+K-1} の中の相異なる要素の個数として、列 B=(B_1, B_2, \ldots, B_N) を作ります。
B_1, B_2, \ldots, B_N が与えられます。この列 B を生成し得た列 A が存在するか判定し、存在する場合はそのような列 A を一つ構成してください。
各入力ファイルについて、T 個のテストケースを解いてください。
制約
- 1 \le T \le 5 \cdot 10^4
- 2 \le N \le 2 \cdot 10^5
- 2 \le K \le 2 \cdot 10^5
- 1 \le B_i \le K
- 各入力ファイル内の N の総和は 2\cdot 10^5 を超えない。
- 各入力ファイル内の K の総和は 2\cdot 10^5 を超えない。
- 入力中のすべての値は整数である。
入力
入力は標準入力から以下の形式で与えられる。
T case_1 case_2 \vdots case_T
各ケースは以下の形式である。
N K B_1 B_2 \ldots B_N
出力
各テストケースについて、題意を満たす列 A が存在しなければ、NO と出力せよ。
そうでなければ、答えを次の形式で出力せよ。
YES
A_1 A_2 \ldots A_{N+K-1}
ここで、1 \leq A_i \leq N+K-1 でなければならず、A は B を生成するものでなければならない。 複数の解が存在する場合は、そのいずれも認められる。
YES または NO の出力において、各文字は英大文字・小文字のいずれでもよい。
入力例 1
3 3 3 1 2 1 4 3 1 2 2 1 6 4 3 3 3 3 3 3
出力例 1
NO YES 1 1 1 2 2 2 YES 1 2 3 1 2 3 1 2 3
Score : 1100 points
Problem Statement
For an integer array A=(A_1, A_2, \ldots, A_{N + K-1}) (1 \leq A_i \leq N+K-1), let's construct an array B=(B_1, B_2, \ldots, B_N), where B_i is the number of distinct elements in A_i,A_{i+1},\ldots,A_{i+K-1}.
You are given B_1, B_2, \ldots, B_N. Determine if there exists an array A which could have produced such an array B, and if yes, construct one.
Solve T test cases for each input file.
Constraints
- 1 \le T \le 5 \cdot 10^4
- 2 \le N \le 2 \cdot 10^5
- 2 \le K \le 2 \cdot 10^5
- 1 \le B_i \le K
- The sum of N in one input file doesn't exceed 2\cdot 10^5.
- The sum of K in one input file doesn't exceed 2\cdot 10^5.
- All values in the input are integers.
Input
Input is given from Standard Input in the following format:
T case_1 case_2 \vdots case_T
Each case is in the following format:
N K B_1 B_2 \ldots B_N
Output
For each test case, if such an array A doesn't exist, output NO.
Otherwise, output the answer in the following format:
YES
A_1 A_2 \ldots A_{N+K-1}
Here, 1 \leq A_i \leq N+K-1 must hold, and A should produce B. If multiple solutions exist, any of them will be accepted.
In printing YES or NO, you can output each letter in any case (upper or lower).
Sample Input 1
3 3 3 1 2 1 4 3 1 2 2 1 6 4 3 3 3 3 3 3
Sample Output 1
NO YES 1 1 1 2 2 2 YES 1 2 3 1 2 3 1 2 3