QOJ.ac

QOJ

حد الوقت: 2 s حد الذاكرة: 256 MB مجموع النقاط: 100 قابلة للهجوم ✓

#14969. Nene 與怪物(簡易版)

الإحصائيات

這是本題的簡易版。兩個版本之間唯一的區別在於 $a_i$ 的限制。只有在兩個版本的問題都解決的情況下,你才能進行 hacks。

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.