提出 #74049944

---

ソースコード 拡げる

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
using P = pair<int, int>;
const ll mod = 998244353;

// #include <atcoder/all>
// using mint = atcoder::modint998244353;
// using namespace atcoder;

int main() {
    int n, s;
    ll q;
    cin >> n >> s >> q;

    vector<int> x(n);
    for (int i=0; i<n; i++) cin >> x[i];
    
    map<int, int> mp;
    for (int i=0; i<n; i++) {
      mp[x[i]] = i;
    }
    
    vector db(61, vector<int>(n));
    for (int i=0; i<n; i++) {
      auto it = mp.find(x[i]);
      
      if (it==mp.begin()) {
        auto nex = next(it);
        db[0][i] = nex->second;
        continue;
      }
      if (it==mp.end()) {
        auto pre = prev(it);
        db[0][i] = pre->second;
        continue;
      }
      
      auto pre = prev(it);
      int pp = pre->first;
      int pi = pre->second;
      auto nex = next(it);
      int np = nex->first;
      int ni = nex->second;
      
      if (abs(x[i]-pp)==abs(x[i]-np)) {
        if (pi<ni) db[0][i] = pi;
        else db[0][i] = ni;
      } else if (abs(x[i]-pp)<abs(x[i]-np)) {
        db[0][i] = pi;
      } else {
        db[0][i] = ni;
      }
    }
    for (int i=1; i<61; i++) {
      for (int j=0; j<n; j++) {
        db[i][j] = db[i-1][db[i-1][j]];
      }
    }
    // for (int i=0; i<n; i++) cout << db[0][i] << " ";
    // cout << endl;
    
    int ans = s-1;
    for (int i=0; i<61; i++) {
      if ((q&(1LL<<i))==0) continue;
      ans = db[i][ans];
    }
    cout << ans+1 << endl;

    return 0;
}

提出情報

ジャッジ結果