Overview

Given \(N\) telescopes arranged on a number line, we repeatedly perform the operation “move to the nearest telescope from the current position” \(Q\) times, and determine the number of the telescope we end up at. Since \(Q\) can be as large as \(10^{18}\), we use cycle detection to compute the answer efficiently.

Analysis

Key Observation 1: The nearest neighbor is an adjacent element in coordinate-sorted order

For any telescope \(i\), the “closest telescope” is either the left neighbor or the right neighbor when sorted by coordinate. This is because any telescope farther away in the sorted array is necessarily farther than an adjacent telescope.

For example, if the coordinates are \([1, 3, 7, 10]\), the nearest telescope to the one at coordinate \(7\) is either \(3\) (distance 4) or \(10\) (distance 3); \(1\) (distance 6) is never a candidate.

Therefore, the “next destination” for each telescope can be precomputed in \(O(1)\).

Key Observation 2: Naive simulation results in TLE

Since \(Q\) can be up to \(10^{18}\), simulating one step at a time is far too slow.

Solution: Cycle Detection

The destination depends solely on the current telescope (the state is a single telescope number), so the transition function \(\text{nxt}[i]\) is deterministic. Since the state space has only \(N\) elements, within at most \(N\) steps we must revisit a previously visited state, creating a cycle.

Once the cycle is detected, we can compute the answer by taking the remaining steps modulo the cycle length.

Algorithm

1. Sort by coordinate: Sort the telescopes by coordinate and record each telescope’s position in the sorted order.
2. Precompute transitions: For each telescope \(i\), compare the distances to the left and right neighbors in sorted order, and set \(\text{nxt}[i]\) to the closer one (if distances are equal, choose the one with the smaller original number).
3. Simulate with cycle detection:
   • Start from telescope \(S\), recording each visited telescope and its step number.
   • When a previously visited telescope is reached, identify the cycle start position \(c\) and cycle length \(L\).
   • The answer is the element at position \(c + (Q - c) \mod L\) in the recorded path.
4. If \(Q\) steps are completed before a cycle is detected, the current telescope is the answer.

Concrete Example

For \(N=3, S=1, Q=5\), coordinates \(X = [0, 2, 3]\):

• \(\text{nxt}[0] = 1\) (telescope 1 → 2, distance 2)
• \(\text{nxt}[1] = 2\) (telescope 2 → 3, distance 1)
• \(\text{nxt}[2] = 1\) (telescope 3 → 2, distance 1)

Path: \(0 \to 1 \to 2 \to 1 \to 2 \to 1\) (0-indexed). At step 3, state 1 is revisited, and the cycle length is \(2\). The answer after \(Q=5\) steps is \(\text{path}[1 + (5-1)\%2] = \text{path}[1] = 1\), which is telescope 2.

Complexity

• Time complexity: \(O(N \log N)\) (sorting) + \(O(N)\) (cycle detection, at most \(N\) steps) = \(O(N \log N)\)
• Space complexity: \(O(N)\) (sorted array, transition array, visit records)

Implementation Notes

• 0-indexed vs 1-indexed conversion: Perform internal processing in 0-indexed and add \(+1\) when outputting.

• Handling equal distances: When the left and right neighbors are equidistant, choose the one with the smaller original number. Note that the comparison is based on original numbers, not positions in sorted order.

• Cycle detection method: Using a dictionary (hash map) to record the first step at which each state is visited is simple and easy to implement. Since there are at most \(N\) states, this is sufficiently fast.

  Source Code

import sys
from bisect import bisect_left

def solve():
    input_data = sys.stdin.buffer.read().split()
    N = int(input_data[0])
    S = int(input_data[1])
    Q = int(input_data[2])
    X = [int(input_data[3 + i]) for i in range(N)]
    
    # For each telescope, precompute the nearest telescope (by distance, then by index)
    # Sort telescopes by coordinate
    # For telescope i, nearest is determined by coordinate neighbors in sorted order
    
    # Create sorted list of (coordinate, original_index)
    telescopes = sorted(range(N), key=lambda i: X[i])
    # sorted_coords[k] = coordinate of the k-th telescope in sorted order
    sorted_coords = [X[telescopes[k]] for k in range(N)]
    # pos_in_sorted[i] = position of telescope i in sorted order
    pos_in_sorted = [0] * N
    for k in range(N):
        pos_in_sorted[telescopes[k]] = k
    
    # For each telescope (by original index i), find nearest telescope
    def get_nearest(i):
        k = pos_in_sorted[i]
        xi = X[i]
        best_dist = float('inf')
        best_idx = -1
        
        # Check left neighbor in sorted order
        if k > 0:
            j = telescopes[k - 1]
            d = xi - X[j]  # positive since sorted
            if d < best_dist or (d == best_dist and j < best_idx):
                best_dist = d
                best_idx = j
        
        # Check right neighbor in sorted order
        if k < N - 1:
            j = telescopes[k + 1]
            d = X[j] - xi  # positive since sorted
            if d < best_dist or (d == best_dist and j < best_idx):
                best_dist = d
                best_idx = j
        
        return best_idx
    
    # The nearest telescope is always one of the adjacent telescopes in sorted coordinate order.
    # So we can precompute next[i] for each telescope i.
    
    nxt = [0] * N
    for i in range(N):
        nxt[i] = get_nearest(i)
    
    # Now we need to follow the chain starting from S-1 (0-indexed) for Q steps.
    # Q can be up to 10^12, so we need cycle detection.
    
    # Since the function is deterministic and the state space is finite (N states),
    # there must be a cycle. Find it.
    
    current = S - 1  # 0-indexed
    
    # Use Floyd's or just track visited states
    # With N up to 2*10^5, we can store the path until we find a repeat
    
    visited = {}
    path = []
    pos = 0
    
    while pos < Q:
        if current in visited:
            # Found cycle
            cycle_start = visited[current]
            cycle_len = pos - cycle_start
            remaining = Q - pos
            remaining_mod = remaining % cycle_len
            # We need to advance remaining_mod more steps from current position
            # But we also need to do the steps from cycle_start to cycle_start + remaining_mod
            # Actually current state at pos is same as at cycle_start
            # So answer is path[cycle_start + (Q - cycle_start) % cycle_len]
            total_remaining = Q - cycle_start
            idx = total_remaining % cycle_len
            print(path[cycle_start + idx] + 1)
            return
        
        visited[current] = pos
        path.append(current)
        current = nxt[current]
        pos += 1
    
    # If we exit without finding cycle, current is the answer
    print(current + 1)

solve()

---

This editorial was generated by claude4.6opus-thinking.