#P13679. [ARC128E] K Different Values

    ID: 12881 传统题 1000ms 256MiB 尝试: 1 已通过: 1 难度: 8 上传者: 标签>CF2500提高+/省选-序列构造暴力枚举不变量分析增量维护

[ARC128E] K Different Values

题目描述

给定一个长度为 NN 的整数序列 A=(A1,A2,⋯ ,AN)A=(A_1, A_2, \cdots, A_N),以及一个整数 KK。

请构造一个整数序列 xx,使其同时满足以下两个条件:

  • 对于每个整数 ii(1≤i≤N1 \leq i \leq N),xx 中恰好包含 AiA_i 个 ii,且不包含其他整数。
  • 在 xx 中,任意连续的 KK 个元素,其值都互不相同。

请判断是否存在满足条件的序列 xx。如果存在,请输出字典序最小的 xx;如果不存在,输出 −1-1。

输入格式

输入通过标准输入给出,格式如下:

NN KK A1A_1 A2A_2 ⋯\cdots ANA_N

输出格式

如果无法构造满足条件的序列 xx,请输出 −1-1。如果可以构造,输出字典序最小的 xx。

输入输出样例 #1

输入 #1

3 3
2 2 1

输出 #1

1 2 3 1 2

输入输出样例 #2

输入 #2

3 2
2 1 2

输出 #2

1 2 3 1 3

输入输出样例 #3

输入 #3

3 3
1 3 3

输出 #3

-1

说明/提示

限制条件

  • 2≤K≤N≤5002 \leq K \leq N \leq 500
  • 1≤Ai1 \leq A_i
  • ∑1≤i≤NAi≤200000\sum_{1 \leq i \leq N} A_i \leq 200000
  • 输入的所有值均为整数

样例解释 1

x=(1,2,3,1,2)x=(1,2,3,1,2) 和 x=(2,1,3,2,1)x=(2,1,3,2,1) 都满足条件,其中字典序最小的是 (1,2,3,1,2)(1,2,3,1,2)。