题解 | #小跳蛙#

找单步跳跃的终点，相当于找到最小的 $d$ ，使得 $[A_i - d, A_i + d]$ 内石头的个数 $\ge n + 1$

对于每个 $i$ ，

左侧石头个数为 $n$ ,右侧石头个数为 $n - i - 1$
考虑取 $lcount$ 个左侧石头和 $rcount = K - lcount$ 个右侧石头
此时取的所有石头中，最左侧石头和最右侧石头的距离为 $dist = \max{(A_i - A_{i - lcount}, A_{i + rcount} - A_i)}$
$dist$ 是一个单峰函数，所以可以用三分法求符合要求的 $lcount$

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

const int inf = 0x3f3f3f3f;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    int n, k;
    ll m;
    cin >> n >> k >> m;

    vector<ll> A(n);

    unordered_map<ll, int> mp;
    for (int i = 0; i < n; ++i){
        cin >> A[i];
        mp[A[i]] = i;
    }

    vector<int> B(n, 0);

    auto f = [&](int idx, int lcount, int rcount){
        ll res = 0;
        if (lcount){
            res = max(res, A[idx] - A[idx - lcount]);
        }
        if (rcount){
            res = max(res, A[idx + rcount] - A[idx]);
        }
        return res;
    };

    for (int i = 0; i < n; ++i){
        int left = i;
        int right = n - 1 - i;

        int l = max(0, k - right);
        int r = min(k, left);

        while (r - l > 3){
            int step = (r - l) / 3;

            int lmid = l + step;
            int rmid = r - step;

            ll f1 = f(i, lmid, k - lmid);
            ll f2 = f(i, rmid, k - rmid);

            if (f1 <= f2){
                r = rmid;
            }
            else{
                l = lmid;
            }
        }

        ll dist = inf;

        for (int lc = l; lc <= r; ++lc){
            int rc = k - lc;
            dist = min(dist, f(i, lc, rc));
        }

        if (mp.count(A[i] - dist)){
            B[i] = mp[A[i] - dist];
        }
        else{
            B[i] = mp[A[i] + dist];
        }

    }

    vector<int> res(n);
    iota(res.begin(), res.end(), 0);

    for (int bit = 0; bit < 60; ++bit){
        if ((m >> bit) & 1){
            vector<int> newres(n);
            for (int i = 0; i < n; ++i){
                newres[i] = B[res[i]];
            }
            swap(res, newres);
        }

        vector<int> newB(n);
        for (int i = 0; i < n; ++i){
            newB[i] = B[B[i]];
        }
        swap(B, newB);
    }

    for (int i = 0; i < n; ++i){
        cout << res[i] + 1 << " \n"[i == n - 1];
    }
}