← 返回题目列表

AtCoder · awc0014_b

B. 马拉松

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

分数: 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