← 返回题目列表

Codeforces · 1601/B

B. 青蛙旅行者

中文机器翻译题面 查看原题

青蛙峡谷正在沼泽王国旅行。不幸的是,在一次失败的跳跃之后,他掉进了一口深$$$n$$$米的井里。现在戈尔夫在井底,向上还有很长的路要走。

井壁的表面质量各不相同:有些地方很滑,但有些地方有方便的壁架。换句话说,如果戈尔夫位于地面以下 $$$x$$$ 米处,那么他一次跳跃就可以上升从 $$$0$$$ 到 $$$a_x$$$ 米(含)的任意整数距离。 (请注意,戈尔夫不能跳下,只能跳上)。

不幸的是,戈尔夫每次跳跃后都必须休息一下(包括跳 $$$0$$$ 米)。在跳到地面以下 $$$x$$$ 米的位置后,他在休息时会向下滑落 $$$b_x$$$ 米。

计算 Gorf 到达地面所需的最小跳跃次数。

输入

第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 300\,000$$$) — 井的深度。

第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \ldots, a_n$$$ ($$$0 \le a_i \le i$$$),其中 $$$a_i$$$ 是 Gorf 可以从地面以下 $$$i$$$ 米跳跃的最大高度。

第三行包含 $$$n$$$ 整数 $$$b_1, b_2, \ldots, b_n$$$ ($$$0 \le b_i \le n - i$$$),其中 $$$b_i$$$ 是 Gorf 在地面以下 $$$i$$$ 米处休息时滑落的距离。

输出

如果 Gorf 无法到达地面,则打印 $$$-1$$$。否则,首先打印整数 $$$k$$$ — 最小可能的跳转次数。

然后打印序列 $$$d_1,\,d_2,\,\ldots,\,d_k$$$,其中 $$$d_j$$$ 是 Gorf 在第 $$$j$$$ 次跳跃之后、但在休息期间滑落之前将达到的深度。地面水平等于 $$$0$$$。

如果有多个答案,请打印其中任何一个。

示例

输入 #1

3
0 2 2
1 1 0

输出 #1

2
1 0

输入 #2

2
1 1
1 0

输出 #2

-1

输入 #3

10
0 1 2 3 5 5 6 7 8 5
9 8 7 1 5 4 3 2 0 0

输出 #3

3
9 4 0

注意

在第一个示例中,Gorf 在井底并跳到地面以下 $$$1$$$ 米的高度。之后,他滑落一米,停留在距地面 $$$2$$$ 米的高度。现在,从这里开始,他可以一跳到达地面。

在第二个示例中,Gorf 可以跳到地面以下一米,但会滑回井底。这就是为什么他无法到达地面。

在第三个示例中,Gorf 只能从地面以下 $$$5$$$ 米的高度到达地面。 Gorf 可以通过一系列跳跃 $$$10 \Rightarrow 9 \dashrightarrow 9 \Rightarrow 4 \dashrightarrow 5$$$ 达到这个高度,其中 $$$\Rightarrow$$$ 是跳跃,$$$\dashrightarrow$$$ 在休息期间滑动。