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$ 是休息时滑落的距离。