CF1601B Frog Traveler
题目描述
青蛙在 $n$ 米深的井中。
对于每一个深度,有两个量 $a_i$ 和 $b_i$。
- $a_i$ 表示在深度为 $i$ 米的时候可以往上跳的最高高度,就是说在深度为 $i$ 米的地方可以往上跳 $\left[0,a_i\right]$ 米。
- $b_i$ 表示在深度为 $i$ 米的地方时会往下滑 $b_i$ 米。
青蛙每跳一次,就会下滑一次。
请求出青蛙最少跳几次可以跳出井(深度为 $0$ 米)。
输入格式
第一行输入一个正整数 $n~(1 \le n \le 3 \times 10^5)$,表示井的深度。
第二行 $n$ 个整数 $a_1, a_2, \cdots, a_n~(0
\le a_i \le i)$,其中 $a_i$ 代表在深度为 $i$ 米的时候可以往上跳的最高高度。
第三行 $n$ 个整数 $b_1, b_2, \cdots, b_n~(0\le b_i\le n-i)$,其中 $b_i$ 表示在深度为 $i$ 米的地方时会往下滑 $b_i$ 米。
输出格式
如果青蛙可以跳出井,输出 $2$ 行,第一行一个正整数表示跳的最少次数 $k$,第二行输出 $k$ 个整数表示跳 $k$ 次之后(下滑前)青蛙位于的深度。
如果青蛙跳不出井,输出 `-1`。
说明/提示
在第一个示例中,青蛙在井底,跳到离地面 $1$ 米的高度。之后他在休息时滑落了 $1$ 米,停留在离地面 $2$ 米的高度。现在,从这里,他可以在一次跳跃中到达地面。
在第二个示例中,青蛙可以跳到离地面 $1$ 米的高度,但会在休息时滑落回井底。这就是他无法到达地面的原因。
在第三个示例中,青蛙只能从离地面 $5$ 米的高度到达地面。它可以通过一系列跳跃 $10 \Rightarrow 9 \dashrightarrow 9 \Rightarrow 4 \dashrightarrow 5$ 到达这个高度,其中 $\Rightarrow$ 是跳跃的距离,$\dashrightarrow$ 是休息时滑落的距离。