E - K Different Values

Contest Duration: 2021-10-16(Sat) 12:00 - 2021-10-16(Sat) 14:00 (local time) (120 minutes) Back to Home

E - K Different Values Editorial

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : $800$ 点

問題文

長さ $N$ の整数列 $A=(A_1,A_2,\cdots,A_N)$ ，及び整数 $K$ が与えられます．

以下の条件を両方満たす整数列 $x$ を作ることを考えます．

各整数 $i$ ( $1 \leq i \leq N$ ) について， $x$ はちょうど $A_i$ 個の $i$ を含む．また逆に，それ以外の整数を含まない．
$x$ の中で連続するどの $K$ 個を見ても，その $K$ 個の値はすべて異なる．

条件を満たす $x$ を作ることが可能かどうか判定し，可能な場合は条件を満たす中で辞書順最小の $x$ を求めてください．

制約

$2 \leq K \leq N \leq 500$
$1 \leq A_i$
$\sum_{1 \leq i \leq N} A_i \leq 200000$
入力される値はすべて整数である

入力

入力は以下の形式で標準入力から与えられる．

 $N$   $K$ 
 $A_1$   $A_2$   $\cdots$   $A_N$

出力

条件を満たす数列 $x$ が作ることが不可能な場合，-1 と出力せよ．可能な場合，辞書順最小の $x$ を出力せよ．

入力例 1Copy

Copy

3 3
2 2 1

出力例 1Copy

Copy

1 2 3 1 2

$x=(1,2,3,1,2),(2,1,3,2,1)$ の二つが条件を満たし，その中で辞書順最小の $(1,2,3,1,2)$ が答えになります．

入力例 2Copy

Copy

3 2
2 1 2

出力例 2Copy

Copy

1 2 3 1 3

入力例 3Copy

Copy

3 3
1 3 3

出力例 3Copy

Copy

-1

Score : $800$ points

Problem Statement

Given are a sequence of $N$ integers $A=(A_1,A_2,\cdots,A_N)$ and an integer $K$ .

Consider making a sequence of integers $x$ that satisfies both of the following conditions.

For each integer $i$ ( $1 \leq i \leq N$ ), $x$ contains exactly $A_i$ occurrences of $i$ . $x$ does not contain other integers.
For every way of choosing $K$ consecutive elements from $x$ , their values are all distinct.

Determine whether it is possible to make $x$ that satisfies the conditions. If it is possible, find the lexicographically smallest such $x$ .

Constraints

$2 \leq K \leq N \leq 500$
$1 \leq A_i$
$\sum_{1 \leq i \leq N} A_i \leq 200000$
All values in input are integers.

Input

Input is given from Standard Input in the following format:

 $N$   $K$ 
 $A_1$   $A_2$   $\cdots$   $A_N$

Output

If it is impossible to make a sequence $x$ that satisfies the conditions, print -1. If it is possible, print the lexicographically smallest such $x$ .

Sample Input 1Copy

Copy

3 3
2 2 1

Sample Output 1Copy

Copy

1 2 3 1 2

Two sequences $x=(1,2,3,1,2),(2,1,3,2,1)$ satisfy the conditions. The lexicographically smaller one, $(1,2,3,1,2)$ , is the answer.

Sample Input 2Copy

Copy

3 2
2 1 2

Sample Output 2Copy

Copy

1 2 3 1 3

Sample Input 3Copy

Copy

3 3
1 3 3

Sample Output 3Copy

Copy

-1