Overview

This problem asks us to find all checkpoints where Takahashi arrives earlier than Aoki (i.e., overtakes Aoki), as both pass through \(N\) checkpoints in order. Specifically, for each checkpoint \(i\) (\(i \geq 2\)), we need to determine whether Takahashi’s arrival time is earlier than Aoki’s arrival time \(T_i\).

Analysis

Calculating Takahashi’s Arrival Time

Takahashi runs at a constant speed \(V\). Let \(S_i\) denote the total distance from checkpoint \(1\) to checkpoint \(i\). Then Takahashi’s arrival time \(A_i\) at checkpoint \(i\) can be expressed as: $\(A_i = \frac{S_i}{V}\)\( Here, \)S_i\( can be computed using the distances \)D_j\( between consecutive checkpoints: \)Si = \sum{j=1}^{i-1} D_j$.

Condition for Overtaking

From the problem statement, the overtaking condition is \(A_i < T_i\). Substituting the expression for \(A_i\): $\(\frac{S_i}{V} < T_i\)$

Avoiding Floating-Point Arithmetic

When handling decimals on a computer, precision errors (rounding errors) can occur. In particular, under this problem’s constraints, \(T_i\) can be up to \(10^{18}\) and the total distance \(S_i\) can be as large as \((2 \times 10^5) \times 10^9 = 2 \times 10^{14}\), so performing division may lead to inaccurate comparisons.

To avoid this, we multiply both sides of the inequality by \(V\) (which is always positive), transforming it into a comparison of integers only: $\(S_i < T_i \times V\)$ This transformation allows us to make exact comparisons without worrying about precision errors.

Magnitude of Values

The maximum value of \(T_i \times V\) can reach \(10^{18} \times 10^9 = 10^{27}\). Since the maximum value of a typical 64-bit integer type (such as long long in C++) is approximately \(9 \times 10^{18}\), overflow must be handled carefully in most programming languages. However, Python’s int type automatically handles arbitrary-precision integers (bignum arithmetic), so such extremely large values can be computed and compared directly.

Algorithm

1. Initialize a variable current_dist to \(0\) to keep track of the cumulative distance.
2. For each checkpoint \(i = 2, 3, \dots, N\), repeat the following:
   • Add \(D_{i-1}\) to current_dist (this gives us \(S_i\)).
   • Check whether the inequality current_dist < T_i * V holds.
   • If it holds, add the checkpoint number \(i\) to the answer list.
3. If the list is empty, output -1; otherwise, output the contents of the list in order.

Complexity

• Time Complexity: \(O(N)\)
  • Since we scan through the checkpoints once, the processing completes in time proportional to \(N\), including input reading.
• Space Complexity: \(O(N)\)
  • The input data and the answer list have sizes proportional to \(N\).

Implementation Notes

• Fast I/O: Since \(N\) can be as large as \(2 \times 10^5\), reading input all at once using sys.stdin.read().split() is faster than calling input() repeatedly, which helps reduce execution time.

• Index Management: Be careful about the correspondence between distances \(D_i\), times \(T_i\), and checkpoint numbers (1-indexed vs. 0-indexed). In the code, i + 2 is used to manage checkpoint numbers.

  Source Code

import sys

def solve():
    # 使用するメモリと時間を最小限にするため、sys.stdin.read().split() で入力を一括読み込みします
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    
    # 全ての入力データを整数に変換します
    # Python 3 の int 型は任意精度（多倍長整数）をサポートしているため、
    # 10^27 などの非常に大きな数値でもオーバーフローの心配なく扱えます
    data = list(map(int, input_data))
    
    # N: チェックポイントの数, V: 高橋君の速さ
    N = data[0]
    V = data[1]
    
    # 2行目の D_i (チェックポイント間の距離) は N-1 個与えられます
    # data[2] から data[N] までが D_1, D_2, ..., D_{N-1} です
    # 3行目の T_i (青木君の到着時刻) は N-1 個与えられます
    # data[N+1] から data[2N-1] までが T_2, T_3, ..., T_N です
    
    ans = []
    current_dist = 0
    
    # 高橋君と青木君は時刻 0 にチェックポイント 1 をスタートします
    # チェックポイント i = 2, 3, ..., N について追い越したかどうかを判定します
    for i in range(N - 1):
        # d_i はチェックポイント i+1 から i+2 までの距離 (D_{i+1})
        d_i = data[i + 2]
        # t_i_plus_2 はチェックポイント i+2 に青木君が到着する時刻 (T_{i+2})
        t_i_plus_2 = data[i + N + 1]
        
        # current_dist はチェックポイント 1 から i+2 までの合計距離 (S_{i+2})
        current_dist += d_i
        
        # 高橋君がチェックポイント i+2 に到着する時刻 A_{i+2} は S_{i+2} / V です
        # 問題文の定義により、A_{i+2} < T_{i+2} のとき、高橋君は追い越したことになります
        # 浮動小数点の精度問題を避けるため、不等式を A_{i+2} < T_{i+2} 
        # すなわち S_{i+2} / V < T_{i+2} を S_{i+2} < T_{i+2} * V に変形して判定します
        if current_dist < t_i_plus_2 * V:
            ans.append(i + 2)
            
    # 追い越したチェックポイントが一つもない場合は -1 を出力します
    if not ans:
        print("-1")
    else:
        # 追い越したチェックポイントの番号を小さい順にスペース区切りで出力します
        print(*(ans))

if __name__ == '__main__':
    solve()

---

This editorial was generated by gemini-3-flash-preview.