分数: 233 分
问题陈述
高桥和青木正在参加马拉松比赛。马拉松赛道有 N 检查站,跑步者按顺序通过它们 1-st 到 N-th。
距 i第一个检查点 (i + 1)第一个检查点是 D_i 米(1 \leq i \leq N-1).
比赛开始时(时间 0 秒),两者同时从 1-st 检查点。
高桥以恒定的速度奔跑,没有任何休息,以 V 米每秒。因此,高桥到达的时间 i第一个检查点 (2 \leq i \leq N) 是 \displaystyle\frac{D_1 + D_2 + \cdots + D_{i-1}}{V} 秒。该值不一定是整数。
另一方面,青木跑的速度不均匀,众所周知,他到达了 i- 第一个检查点恰好在时间 T_i 秒。在这里, T_1 = 0。青木的到达时间满足 T_1 < T_2 < T_3 < \cdots < T_N.
对于每个检查点 i 来自 2-nd 向前 (2 \leq i \leq N),如果高桥的到达时间是 严格小于 青木到达时间 T_i,也就是说,如果
D_1 + D_2 + \cdots + D_{i-1} < T_i \times V
成立,那么据说高桥有 首先到达 在检查站 i 领先青木。如果同时到达,不算先到。
找出高桥先于青木先到达的所有检查点编号,并按升序输出。如果没有这样的检查点,则输出 -1.
约束
- 2 \leq N \leq 2 \times 10^5
- 1 \leq V \leq 10^9
- 1 \leq D_i \leq 10^9 (1 \leq i \leq N-1)
- T_1 = 0
- 1 \leq T_i \leq 10^{18} (2 \leq i \leq N)
- T_i < T_{i+1} (1 \leq i \leq N-1)
- 所有输入值均为整数。
输入
N V
D_1 D_2 \cdots D_{N-1}
T_2 T_3 \cdots T_N
- 第一行包含检查点的数量 N 和高桥的速度 V (米每秒),以空格分隔。
- 第二行包含 N - 1 距离 D_i (米)距 i第一个检查点 (i + 1)- 第一个检查点(按顺序排列) i = 1, 2, \ldots, N-1),用空格分隔。
- 第三行包含 N - 1 到达时间 T_i (秒)青木到达 输入中不包含 i- 第一个检查点(按顺序排列) i = 2, 3, \ldots, N),用空格分隔。 T_1 = 0 。
输出
在一行中按升序输出高桥先于青木首先到达的检查站编号,以空格分隔。如果没有这样的检查点,则输出 -1.
示例输入 1
5 10 30 50 40 60 4 10 15 20
示例输出 1
2 3 4 5
示例输入 2
4 5 100 100 100 10 20 30
示例输出 2
-1
示例输入 3
8 100 500 300 700 200 400 600 800 4 8 20 25 35 50 80
示例输出 3
4 5 6 7 8