← 返回题目列表

AtCoder · agc059_d

D. 子段上的不同元素

中文机器翻译题面 查看原题

分数: 1100 点

问题陈述

对于整数数组 A=(A_1, A_2, \ldots, A_{N + K-1}) (1 \leq A_i \leq N+K-1),让我们构造一个数组 B=(B_1, B_2, \ldots, B_N),其中 B_i 是不同元素的数量 A_i,A_{i+1},\ldots,A_{i+K-1}.

你被给予 B_1, B_2, \ldots, B_N。判断是否存在数组 A 可以产生这样的数组 B,如果是,则构建一个。

解决 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 or 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