Overview

This is a problem where you simulate movement between telescopes placed on a number line and determine which telescope you are at after \(Q\) moves.

Analysis

In this problem, the coordinates of each telescope are given, and the participant moves to the nearest different telescope from their current position. However, they cannot return to the position they were at immediately before.

Naively simulating one move at a time would require up to \(Q = 10^{18}\) moves in the worst case, which is not feasible (too slow). However, since the movement is performed deterministically, it is guaranteed that after enough time, the state will return to some previously visited state (i.e., the movement has periodicity).

Therefore, we can use a “cycle detection method” to find the loop in the movement and efficiently determine the state after \(Q\) moves.

Additionally, to quickly find the nearest neighbor for each telescope, it suffices to only consider adjacent elements in the coordinate-sorted array. This eliminates the need for a full search each time.

Algorithm

1. First, create pairs of telescope coordinates \(X_i\) and their indices \(i\), and sort them by coordinate.
2. For each telescope, preprocess the left and right neighboring telescopes in the sorted list.
3. Define a function get_next that determines the next telescope to move to from the current position:
   • Compare the distances to the left and right neighboring telescopes of the current telescope, and choose the closest one (with the smaller index in case of ties).
4. Starting from the initial position, simulate the movement while recording visited states, and find the cycle.
5. Determine the starting position and length of the cycle, and calculate which position \(Q\) corresponds to.
6. Output the telescope number corresponding to the final position.

Complexity

• Time complexity: \(O(N \log N)\) (mainly due to sorting and initialization via binary search)
• Space complexity: \(O(N)\)

Implementation Notes

• Accurately manage the correspondence between sorted indices and original indices.

• Cycle detection is performed by recording visited positions using a dictionary or similar structure.

• bisect_left is used to convert the initial position to an index in the sorted array.

• Updating left and right adjacent elements is unnecessary (since they don’t move), so preprocessing alone is sufficient.

  Source Code

import sys
from bisect import bisect_left

def main():
    import sys
    input = sys.stdin.read
    data = input().split()
    
    N = int(data[0])
    S = int(data[1])
    Q = int(data[2])
    X = list(map(int, data[3:3+N]))
    
    # 座標とインデックスのペアを作成し、座標でソート
    indexed_X = [(X[i], i+1) for i in range(N)]
    indexed_X.sort()
    sorted_X = [x[0] for x in indexed_X]
    original_index = [x[1] for x in indexed_X]
    
    # 座標から元のインデックスへのマップ
    pos_to_idx = {x[0]: x[1] for x in indexed_X}
    
    # 各位置における左右の隣接要素を前処理
    left_neighbor = [-1] * N
    right_neighbor = [-1] * N
    
    for i in range(N):
        if i > 0:
            left_neighbor[i] = i - 1
        if i < N - 1:
            right_neighbor[i] = i + 1
    
    # シミュレーション用の関数
    def get_next(current_idx_zero):
        x_curr = sorted_X[current_idx_zero]
        candidates = []
        
        # 左の候補
        l = left_neighbor[current_idx_zero]
        if l != -1:
            dist_l = abs(x_curr - sorted_X[l])
            candidates.append((dist_l, original_index[l], l))
            
        # 右の候補
        r = right_neighbor[current_idx_zero]
        if r != -1:
            dist_r = abs(x_curr - sorted_X[r])
            candidates.append((dist_r, original_index[r], r))
            
        if not candidates:
            return None
            
        candidates.sort()
        _, _, next_idx_zero = candidates[0]
        return next_idx_zero
    
    # 現在位置（ソート後のインデックス）
    current_pos = bisect_left(sorted_X, X[S-1])
    
    # パスの検出
    visited = {}
    path = []
    steps = 0
    pos_in_path = current_pos
    
    while True:
        if current_pos in visited:
            cycle_start = visited[current_pos]
            cycle_length = steps - cycle_start
            break
        visited[current_pos] = steps
        path.append(current_pos)
        steps += 1
        next_pos = get_next(current_pos)
        if next_pos is None:
            # 移動できない場合（あり得ないが念のため）
            cycle_start = steps
            cycle_length = 1
            path.append(current_pos)
            break
        current_pos = next_pos
        
    # Qステップ後の位置を計算
    if Q < cycle_start:
        final_pos_sorted = path[Q]
    else:
        Q_adjusted = (Q - cycle_start) % cycle_length
        final_pos_sorted = path[cycle_start + Q_adjusted]
        
    print(original_index[final_pos_sorted])

if __name__ == "__main__":
    main()

---

This editorial was generated by qwen3-coder-480b.