Overview

This problem asks you to find your position after making \(Q\) moves on a number line with \(N\) telescopes, following the rule of always moving to the nearest telescope from your current location.

Analysis

Since \(Q\) can be as large as \(10^{18}\), naively simulating each move one by one would result in TLE (Time Limit Exceeded).

However, the movement rule in this problem has an important property: “the next destination is uniquely determined solely by the current telescope.” Since there are only \(N\) telescopes (at most \(2 \times 10^5\)), after continuing to move, you will inevitably reach a previously visited telescope within \(N\) steps. Once you return to a previously visited telescope, you will repeat the exact same path infinitely (entering a loop). By exploiting this “loop (periodicity),” we can skip the enormous remaining number of moves at once using the remainder of a division.

Also, when searching for the nearest telescope from a given telescope, checking all telescopes each time would cost \(O(N)\). However, if we sort the telescopes by coordinate in advance, the candidates for the nearest telescope are narrowed down to just the “left neighbor” and “right neighbor.”

Algorithm

1. Preprocessing (Determining Movement Destinations)
   • Store the telescope information as (coordinate, original index) pairs in an array, and sort in ascending order of coordinates.
   • For each telescope in the sorted order, determine the index of the next telescope to move to, nxt[i].
     • The leftmost telescope always moves to its right neighbor, and the rightmost telescope always moves to its left neighbor.
     • For all other telescopes, compare the distances to the left and right neighbors, and move to the closer one. If the distances are equal, choose the one with the smaller “original index” according to the problem’s conditions.
2. Loop Detection and Simulation
   • Start from the initial position \(S\) and simulate movement according to nxt.
   • During this process, record “at which step each telescope was reached” in an array visited, and sequentially append the movement history to an array path.
   • If, before completing \(Q\) moves, you reach a telescope that already has a record in visited (i.e., was previously visited), you know that a loop has been entered.
3. Computing the Answer
   • Let loop_start be the step at which the loop begins, and loop_len be the period (length of one cycle) of the loop.
   • At the point when the loop is detected, the remaining number of moves is Q - loop_start. Divide this by the period loop_len and let rem be the remainder.
   • The final position is the telescope recorded at position loop_start + rem in the movement history path.

Complexity

• Time complexity: \(O(N \log N)\)
  • Sorting the telescope coordinates takes \(O(N \log N)\).
  • Determining the movement destination for each telescope (building nxt) takes \(O(N)\).
  • The simulation detects a loop in at most \(N\) steps, so it completes in \(O(N)\).
  • Overall, this is \(O(N \log N)\), which is sufficiently fast under the given constraints.
• Space complexity: \(O(N)\)
  • \(O(N)\) memory is used to store the telescope coordinate data, the movement destination array nxt, the visit record visited, the path record path, etc.

Implementation Notes

• Preserving original indices: Since sorting by coordinate scrambles the original numbering (1 to N), it is important to store the data as (coordinate, index) pairs before sorting.

• Handling equal distances: When distances are equal, you select the “telescope with the smallest index,” but note that the comparison should use the “original telescope index,” not the “index after sorting.”

• Index management: In languages like Python, array indices start from 0, but telescope numbers start from 1. Setting the size of arrays nxt and visited to \(N+1\) so that telescope numbers can be used directly as indices makes the implementation simpler and less prone to bugs.

  Source Code

import sys

def solve():
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    
    N = int(input_data[0])
    S = int(input_data[1])
    Q = int(input_data[2])
    
    X = [(int(input_data[3+i]), i+1) for i in range(N)]
    X.sort(key=lambda x: x[0])
    
    nxt = [0] * (N + 1)
    nxt[X[0][1]] = X[1][1]
    nxt[X[-1][1]] = X[-2][1]
    
    for j in range(1, N - 1):
        idx = X[j][1]
        l_idx = j - 1
        r_idx = j + 1
        
        dist_l = X[j][0] - X[l_idx][0]
        dist_r = X[r_idx][0] - X[j][0]
        
        if dist_l < dist_r:
            nxt[idx] = X[l_idx][1]
        elif dist_l > dist_r:
            nxt[idx] = X[r_idx][1]
        else:
            nxt[idx] = min(X[l_idx][1], X[r_idx][1])
            
    visited = [-1] * (N + 1)
    path = []
    
    curr = S
    step = 0
    
    while True:
        if step == Q:
            print(curr)
            return
            
        if visited[curr] != -1:
            loop_start = visited[curr]
            loop_len = step - loop_start
            rem = (Q - loop_start) % loop_len
            print(path[loop_start + rem])
            return
            
        visited[curr] = step
        path.append(curr)
        curr = nxt[curr]
        step += 1

if __name__ == '__main__':
    solve()

This editorial was generated by gemini-3.1-pro-thinking.