Overview

When telescopes are arranged on a number line, “moving to the nearest telescope” uniquely determines the next destination from each telescope, so this reduces to \(Q\) transitions on a directed graph (where each vertex has out-degree 1). Then we find the cycle (period) to compute the answer quickly even when \(Q\) is large.

Analysis

Key Observation

For points on a number line, the nearest telescope to a given telescope \(i\) (at coordinate \(X_i\)) is limited to one of its immediate neighbors when sorted by coordinate.

• For example, if the coordinates are arranged as \(\cdots < a < b < c < \cdots\) and we are currently at \(b\), then the closest candidates from \(b\) are only \(a\) or \(c\).
  Any point to the left of \(a\) is necessarily farther than \(a\), and any point to the right of \(c\) is necessarily farther than \(c\).

Therefore, the “next telescope to move to” for each telescope can be determined in $O(1) (as long as we know the left and right neighbors): - If it’s an endpoint, the single neighbor is determined - Otherwise, compare the left and right neighbors and choose the closer one - If the distances are equal, choose the one with the smaller index

Why the Naive Approach Fails

• If we check “the distance to all telescopes” for each move, it’s \(O(N)\) per move, and \(O(NQ)\) for \(Q\) moves, which is impossible since \(Q \le 10^{18}\).
• Even if we know the next destination, directly simulating \(Q\) moves is \(O(Q)\), which is also impossible.

How to Solve It

• First, precompute the transition destination \(nxt[i]\) for each telescope \(i\) (sort by coordinate + compare neighbors).
• Since “current position → next telescope” is always uniquely determined, the whole structure forms a Functional Graph (a graph with out-degree 1).
• When traversing a Functional Graph, we always revisit the same vertex and enter a cycle, so by finding:
  • The length of the tail (prefix before the cycle)
  • The length of the cycle
    we can determine the position in one step using modular arithmetic even when \(Q\) is enormous.

Algorithm

1. Sort the telescopes by coordinate and create an array pts = [(coordinate, index), ...].
2. For each element pts[k], determine the next destination nxt[index].
   • If \(k=0\) (leftmost), move to the right neighbor
   • If \(k=N-1\) (rightmost), move to the left neighbor
   • Otherwise, compare the distances to the left and right neighbors pts[k-1], pts[k+1]
     • \(dl = X_k - X_{k-1}\), \(dr = X_{k+1} - X_k\)
     • If \(dl<dr\), go left; if \(dr<dl\), go right
     • If \(dl=dr\), choose the one with the smaller index
3. Starting from the initial position S, follow pos = nxt[pos] and record the first visit time of each telescope in visited[pos].
   • If not yet visited, continue advancing
   • If we reach an already-visited vertex, a cycle starts from there
4. Compute the answer using cycle_start (the time when the cycle begins) and cycle_len (the cycle length).
   • If \(Q < cycle\_start\): we are in the tail portion, so the answer is order[Q]
   • Otherwise: we are in the cycle, so the answer is
     order[cycle_start + (Q - cycle_start) % cycle_len]

Complexity

• Time complexity: \(O(N \log N)\) (coordinate sorting) + \(O(N)\) (determining transitions and detecting the cycle), giving an overall \(O(N \log N)\)
• Space complexity: \(O(N)\) (for nxt, visited, order, etc.)

Implementation Notes

• “The nearest telescope” can be found by only looking at neighbors in sorted coordinate order (this observation is the most important).

• The tiebreaker when distances are equal is the telescope with the smaller index, so when left and right are equidistant, choose min(iL, iR).

• For cycle detection, by storing “the step number of the first visit” in visited:

  • Cycle start position: cycle_start = visited[pos]
  • Cycle length: cycle_len = step - cycle_start can be easily computed.

• Since \(Q\) can be up to \(10^{18}\), we must always compute using modular arithmetic with the cycle length.

  Source Code

import sys

def main():
    it = iter(sys.stdin.buffer.read().split())
    N = int(next(it))
    S = int(next(it))
    Q = int(next(it))
    X = [int(next(it)) for _ in range(N)]

    pts = sorted((X[i], i + 1) for i in range(N))  # (coord, index)
    nxt = [0] * (N + 1)

    for k, (x, idx) in enumerate(pts):
        if k == 0:
            nxt[idx] = pts[1][1]
        elif k == N - 1:
            nxt[idx] = pts[N - 2][1]
        else:
            xL, iL = pts[k - 1]
            xR, iR = pts[k + 1]
            dl = x - xL
            dr = xR - x
            if dl < dr:
                nxt[idx] = iL
            elif dr < dl:
                nxt[idx] = iR
            else:
                nxt[idx] = iL if iL < iR else iR

    visited = [-1] * (N + 1)
    order = []
    pos = S
    step = 0
    while visited[pos] == -1:
        visited[pos] = step
        order.append(pos)
        pos = nxt[pos]
        step += 1

    cycle_start = visited[pos]
    cycle_len = step - cycle_start

    if Q < cycle_start:
        ans = order[Q]
    else:
        ans = order[cycle_start + (Q - cycle_start) % cycle_len]

    sys.stdout.write(str(ans) + "\n")

if __name__ == "__main__":
    main()

This editorial was generated by gpt-5.2-high.