题解：AT_arc187_a [ARC187A] Add and Swap

次数限制这么松，该考虑我们随机化算法了！

首先有一个想法是朴素的冒泡排序，操作 a,b 会变为 b+k,a，若 a > b 且 b+k>a，则操作后并无法改变两数相对顺序。

我们考虑随机化，进行至多 5 \times 10^5 轮，每轮随机一个 1 到 n 的排列 p_1,p_2,\cdots,p_n，按照如下操作，直到 a 排好序：

1. 找到最小的 i，使得 p_i \neq n，a_{p_i} > a_{p_{i}+1} 且 a_{p_{i}+1}+k \leq a_{p_i}，对 p_i 进行操作。若不存在这样的 i，进行第 2 步。
2. 找到最小的 i，使得 p_i \neq n 且 a_{p_{i}+1} + k \leq a_{p_i}，对 p_i 操作。若不存在这样的 i，进行第 3 步。
3. 找到最小的 i，使得 p_i \neq n，操作 p_i。

实测操作次数不超过 1.5 \times 10^5，可以通过。无解当且仅当 n=2 且 a_2 + k > a_1。

代码：

int cnt = 0;
while (cnt < (int)5e5 && !is_sorted(a.begin() + 1, a.begin() + n + 1))
{
    shuffle(p.begin() + 1, p.begin() + n + 1, rnd);
    bool tag = 0;
    for (int i = 1; i <= n; i++)
    {
        int j = p[i];
        if (j != n && a[j] > a[j + 1] && a[j + 1] + k <= a[j])
        {
            tag = 1;
            pushans(j);
            cnt++;
            break;
        }
    }
    if (!tag)
    {
        for (int i = 1; i <= n; i++)
        {
            int j = p[i];
            if (j != n && a[j + 1] + k <= a[j])
            {
                tag = 1;
                pushans(j);
                cnt++;
                break;
            }
        }
        if (!tag)
        {
            for (int i = 1; i <= n; i++)
            {
                int j = p[i];
                if (j != n)
                {
                    tag = 1;
                    pushans(j);
                    cnt++;
                    break;
                }
            }
        }
    }
}