AT_joi2025_yo2_b.ビリヤード (Billiards)

通过率：0%

AC君温馨提醒

该题目为【atcoder】题库的题目，您提交的代码将被提交至atcoder进行远程评测，并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供，我们无法保证该服务的稳定性，若提交后无反应，请等待一段时间后再进行重试。

比太郎正在玩台球。在 JOI 国的台球游戏中，会使用放置在台面上的 $N$ 个球，标号为 $1, 2, \dots, N$ 。台面上设有用来将球打入的洞。被打入洞中的球不会回到台面上，也不能再次被打入。比太郎的目标是尽可能打入洞中的球中编号最大者。

击球是一项需要集中注意力的工作。起初，比太郎的集中力为 $X$ ，将第 $i$ 个球打入洞中会消耗 $A_i$ 的集中力。当比太郎的集中力小于 $A_i$ 时，他不能将第 $i$ 个球打入洞中。

此外，在本台球规则下，对于打球的顺序也有规定。具体来说，当 $P_i=-1$ （ $1\leq i\leq N$ ）时，第 $i$ 个球可以在任何时候被打入；当 $P_i \neq -1$ 时，要打入第 $i$ 个球，必须先将第 $P_i$ 个球打入洞中。

给定比太郎的集中力和每个球的信息，请判断他能否打球，并在可以打球的情况下求出他能够打入洞中的球的最大编号。如果一个球也不能打入洞中，则输出 $-1$ 。

输入格式如下：

$N$ $X$ $A_1$ $A_2$ $\dots$ $A_N$ $P_1$ $P_2$ $\dots$ $P_N$

输出比太郎能打入洞中的最大球编号，如果一个球也不能打入，则输出 $-1$ 。

输入#5

9 2468024680
123456789 234567891 345678912 456789123 567891234 678912345 789123456 891234567 912345678
6 5 4 -1 3 2 1 9 8

输出#5

子任务

起初，比太郎的集中力为 $7$ 。
对全部 $i$ （ $1\leq i\leq N$ ）都满足 $P_i=-1$ ，因此比太郎只要集中力足够，可以任意顺序将球打入洞中。

例如，可以像这样操作，比太郎可以将编号为 $4$ 的球打入洞中：

此外，比太郎无法将编号为 $5$ 和 $6$ 的球打入洞中。因此，比太郎能打入洞中的球的最大编号为 $4$ 。

该输入样例符合子任务 $1, 3, 4, 5, 6$ 的约束条件。

起初，比太郎的集中力为 $12$ 。
例如，可以像这样操作，比太郎可以将编号为 $4$ 的球打入洞中：

首先，将第 $1$ $1$ 个球打入洞中（ $P_1 = -1$ $P_{1} = - 1$ ，因此第 $1$ $1$ 个球可随时打入）。
- 集中力减少 $1$ ，剩余 $11$ 。
接着，将第 $2$ $2$ 个球打入洞中（ $P_2 = 1$ $P_{2} = 1$ ，且第 $1$ $1$ 个球已打入，因此可以打第 $2$ $2$ 个球）。
- 集中力减少 $2$ ，剩余 $9$ 。
再将第 $3$ $3$ 个球打入洞中（ $P_3 = 2$ $P_{3} = 2$ ，且第 $2$ $2$ 个球已打入，因此可以打第 $3$ $3$ 个球）。
- 集中力减少 $3$ ，剩余 $6$ 。
最后，将第 $4$ $4$ 个球打入洞中（ $P_4 = 3$ $P_{4} = 3$ ，且第 $3$ $3$ 个球已打入，因此可以打第 $4$ $4$ 个球）。
- 集中力减少 $5$ ，剩余 $1$ 。

比太郎无法将编号为 $5$ 的球打入洞中。因此，比太郎能打入洞中的球的最大编号为 $4$ 。

该输入样例符合子任务 $2, 3, 4, 5, 6$ 的约束条件。

该输入样例符合子任务 $3, 4, 5, 6$ 的约束条件。

由于 $P_1 = 2$ ，要打入第 $1$ 个球，必须先打第 $2$ 个球；同理， $P_2 = 1$ ，要打入第 $2$ 个球，必须先打第 $1$ 个球。由此，比太郎无法打入任何球。因此，输出 $-1$ 。

该输入样例符合子任务 $5, 6$ 的约束条件。

该输入样例符合子任务 $5, 6$ 的约束条件。

由 ChatGPT 5 翻译

输入解题思路，AI测评打分。不知道怎么写?