ある望遠鏡から次にどの望遠鏡へ移動するかは、それが何度目の移動かに依らず一定です。よって高々 \(N\) 回の移動で既に到達したことのある望遠鏡に再到達したあとは同じ移動を繰り返すことになります。

特に今回の条件下では \(N\) 回の移動より後では、隣り合う \(2\) つの望遠鏡の間を行き来する状態に到達します。

予め望遠鏡を座標順にソートしておくことで、 1 回の移動は \(O(1)\) でシミュレーションできるため、 \(Q \leq N\) のときは愚直にシミュレーションし、\(Q>N\) のときは \(Q\) の偶奇に応じて、\(N\) 回目または \(N+1\) 回目の移動後の望遠鏡の番号を答えることで、この問題を \(O(N\log N)\) で解くことができます。

番兵として、座標の絶対値が十分大きな箇所にも望遠鏡があるとみなすと端での処理の場合分けをなくすことができます。

実装例 (C++)

#include<bits/stdc++.h>
using namespace std;

int main(){
  int n, s;
  long long q;
  cin >> n >> s >> q;
  vector<int>x(n);
  for(int i=0; i<n; i++) cin >> x[i];

  vector<pair<long long,int>>xi(n);
  for(int i=0; i<n; i++){
    xi[i] = {x[i], i+1};
  }
  xi.push_back({1000000000000000000,-1});
  xi.push_back({-1000000000000000000,-1});
  sort(xi.begin(), xi.end());

  int crr_pos = -1;
  for(int pos=0; pos<xi.size(); pos++){
    if(xi[pos].second == s){
      crr_pos = pos;
    }
  }

  auto calc_next_pos = [&](int crr_pos){
    long long left = xi[crr_pos].first - xi[crr_pos - 1].first;
    long long right = xi[crr_pos + 1].first - xi[crr_pos].first;
    if((left < right) || (left == right && xi[crr_pos - 1].second < xi[crr_pos + 1].second)){
      return crr_pos - 1;
    }else{
      return crr_pos + 1;
    }
  };

  if(q < n){
    for(int i=0; i<q; i++){
      crr_pos = calc_next_pos(crr_pos);
    }
  }else{
    for(int i=0; i<n; i++){
      crr_pos = calc_next_pos(crr_pos);
    }
    if(n % 2 != q % 2){
      crr_pos = calc_next_pos(crr_pos);
    }
  }
  cout << xi[crr_pos].second << endl;
}

実装例 (Python)

N, S, Q = map(int, input().split())
X = list(map(int, input().split()))
XI = [(x, i) for i, x in enumerate(X, 1)]
XI.append((10**18, -1))
XI.append((-10**18, -1))

XI.sort()

for pos, (x, i) in enumerate(XI):
  if i == S:
    crr_pos = pos

def calc_next_pos(crr_pos):
  left = XI[crr_pos][0] - XI[crr_pos - 1][0]
  right = XI[crr_pos + 1][0] - XI[crr_pos][0]
  if (left < right) or (left == right and XI[crr_pos - 1][1] < XI[crr_pos + 1][1]):
    return crr_pos - 1
  else:
    return crr_pos + 1

if Q < N:
  for _ in range(Q):
    crr_pos = calc_next_pos(crr_pos)
else:
  for _ in range(N):
    crr_pos = calc_next_pos(crr_pos)
  if N % 2 != Q % 2:
    crr_pos = calc_next_pos(crr_pos)

print(XI[crr_pos][1])