QOJ.ac

QOJ

시간 제한: 3.0 s 메모리 제한: 512 MB 총점: 100

#15994. 龙争虎斗

통계

阿尔德尼亚(Ardenia)的首都周围有几个湖泊,每个湖泊最初都是满水的。目前,预计该地区将有暴雨。暴雨会降落在其中一个湖泊上:如果该湖泊是干涸且空的,它将被水填满;如果该湖泊已经是满的,它就会溢出,从而导致自然灾害。幸运的是,市民们有一条龙可以使用(他们会毫不犹豫地使用它)。这条龙可以一次性喝光一个湖泊里的所有水。此外,阿尔德尼亚的法师们已经预测了未来几年的天气情况。唯一的问题是:龙应该在什么时候喝哪个湖泊的水,以防止灾难发生?

输入包含多个测试用例。输入的第一行包含一个正整数 $Z \le 40$,表示测试用例的数量。接下来是 $Z$ 个测试用例,每个测试用例都符合“输入格式”一节中描述的格式。对于每个测试用例,你的程序必须输出符合“输出格式”一节中描述的格式的内容。

输入格式

每个测试用例的第一行包含两个空格分隔的正整数 $n \le 10^6$ 和 $m \le 10^6$,其中 $n$ 是湖泊的数量。(最多有 10 个测试用例满足 $n \ge 10^5$ 或 $m \ge 10^5$。)

第二行包含未来 $m$ 天的天气预报:$m$ 个空格分隔的整数 $t_1, t_2, \dots, t_m$($t_i \in [0, n]$)。如果 $t_i \in [1, n]$,表示第 $i$ 天湖泊 $t_i$ 将降下暴雨。如果 $t_i = 0$,表示第 $i$ 天不下雨,龙有时间选择喝掉其中一个湖泊的水。请注意,龙在下雨天不会喝水。

输出格式

对于每个测试用例,如果可以防止灾难性的溢出,你的程序应该在第一行输出单词 YES,否则输出 NO

在前一种情况下(即输出 YES 时),你还应该输出第二行,包含 $\ell$ 个范围在 $[0, n]$ 内的整数,其中 $\ell$ 是天气预报描述中 $0$ 的个数,即不下雨的天数。这些整数中的每一个表示龙应该喝水的湖泊编号;$0$ 表示龙不应该喝任何湖泊的水(这可能是必要的,因为即使是龙也不能从空湖泊中喝水)。

样例

输入 1

4
2 4
0 0 1 1
2 4
0 1 0 2
2 3
0 1 2
2 4
0 0 0 1

输出 1

NO
YES
1 2
NO
YES
0 1 0

Discussions

About Discussions

The discussion section is only for posting: General Discussions (problem-solving strategies, alternative approaches), and Off-topic conversations.

This is NOT for reporting issues! If you want to report bugs or errors, please use the Issues section below.

Open Discussions 0
No discussions in this category.

Issues

About Issues

If you find any issues with the problem (statement, scoring, time/memory limits, test cases, etc.), you may submit an issue here. A problem moderator will review your issue.

Guidelines:

  1. This is not a place to publish discussions, editorials, or requests to debug your code. Issues are only visible to you and problem moderators.
  2. Do not submit duplicated issues.
  3. Issues must be filed in English or Chinese only.
Active Issues 0
No issues in this category.
Closed/Resolved Issues 0
No issues in this category.