QOJ.ac

QOJ

実行時間制限: 2 s メモリ制限: 256 MB 満点: 100 ハック可能 ✓

#16905. Nene vs. Monsters (简单版)

統計

这是该问题的简单版本。两个版本之间唯一的区别是对 $a_i$ 的限制。只有当两个版本都被解决时,你才能进行 Hack。

Nene 正在与围成一圈的 $n$ 个怪物战斗。这些怪物的编号为 $1$ 到 $n$,第 $i$($1 \le i \le n$)个怪物当前的能量值为 $a_i$。

由于怪物们太强大了,Nene 决定使用“攻击你的邻居”(Attack Your Neighbour)法术来与它们战斗。当 Nene 使用这个法术时,以下事件将依次发生:

  • 第 $1$ 个怪物攻击第 $2$ 个怪物;
  • 第 $2$ 个怪物攻击第 $3$ 个怪物;
  • ……
  • 第 $(n-1)$ 个怪物攻击第 $n$ 个怪物;
  • 第 $n$ 个怪物攻击第 $1$ 个怪物。

当能量值为 $x$ 的怪物攻击能量值为 $y$ 的怪物时,防御怪物的能量值变为 $\max(0, y-x)$(攻击怪物的能量值保持 $x$ 不变)。

Nene 打算使用这个法术 $10^{100}$ 次,然后亲自解决那些能量值仍不为零的怪物。她希望你帮她确定,在她使用上述法术 $10^{100}$ 次后,哪些怪物会拥有非零的能量值。

输入格式

每个测试点包含多个测试用例。第一行包含测试用例的数量 $t$($1 \le t \le 10^4$)。接下来是测试用例的描述。

每个测试用例的第一行包含一个整数 $n$($2 \le n \le 2 \cdot 10^5$)—— 怪物的数量。

第二行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n$($0 \le a_i \le 2 \cdot 10^5$)—— 怪物们当前的能量值。

保证所有测试用例中 $n$ 的总和不超过 $2 \cdot 10^5$。

输出格式

对于每个测试用例:

  • 第一行输出一个整数 $m$ —— 在使用法术 $10^{100}$ 次后,能量值非零的怪物数量;
  • 第二行输出 $m$ 个整数 $i_1, i_2, \ldots, i_m$($1 \le i_1 < i_2 < \ldots < i_m \le n$)—— 这些怪物的编号,按升序排列。

如果 $m=0$,你可以输出一个空行,也可以不输出。

样例

输入 1

5
3
2 5 3
2
0 0
4
1 5 7 2
4
4 2 1 2
13
1 1 4 5 1 4 1 9 1 9 8 1 0

输出 1

1
1 
0

1
1 
2
1 3 
6
1 3 6 8 10 12

说明

在第一个测试用例中,在前 $3$ 次使用法术期间,依次发生以下事件:

  • Nene 第一次使用“攻击你的邻居”法术;
  • 第 $1$ 个怪物攻击第 $2$ 个怪物,攻击后第 $2$ 个怪物的能量值变为 $\max(0, 5-2)=3$;
  • 第 $2$ 个怪物攻击第 $3$ 个怪物,攻击后第 $3$ 个怪物的能量值变为 $\max(0, 3-3)=0$;
  • 第 $3$ 个怪物攻击第 $1$ 个怪物,攻击后第 $1$ 个怪物的能量值变为 $\max(0, 2-0)=2$;
  • Nene 第二次使用“攻击你的邻居”法术;
  • 第 $1$ 个怪物攻击第 $2$ 个怪物,攻击后第 $2$ 个怪物的能量值变为 $\max(0, 3-2)=1$;
  • 第 $2$ 个怪物攻击第 $3$ 个怪物,攻击后第 $3$ 个怪物的能量值变为 $\max(0, 0-1)=0$;
  • 第 $3$ 个怪物攻击第 $1$ 个怪物,攻击后第 $1$ 个怪物的能量值变为 $\max(0, 2-0)=2$;
  • Nene 第三次使用“攻击你的邻居”法术;
  • 第 $1$ 个怪物攻击第 $2$ 个怪物,攻击后第 $2$ 个怪物的能量值变为 $\max(0, 1-2)=0$;
  • 第 $2$ 个怪物攻击第 $3$ 个怪物,攻击后第 $3$ 个怪物的能量值变为 $\max(0, 0-0)=0$;
  • 第 $3$ 个怪物攻击第 $1$ 个怪物,攻击后第 $1$ 个怪物的能量值变为 $\max(0, 2-0)=2$。

在接下来的每次使用法术后,怪物的能量值都不会再改变。因此,最终只有第 $1$ 个怪物拥有非零的能量值。

在第二个测试用例中,两个怪物初始的能量值都为零。

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.