Жертва (Розбір)

Поради:

1) Зверніть увагу, що будь-яка кількість обмінів еквівалентна перестановці масиву в будь-який масив.

2) Значення $m$ не має значення в фактичному значенні.

3) Оптимальний спосіб - відсортувати масив у порядку спадання та вибрати цілі числа на основі цього.

4) Перевірка для задачі - перевірка повних циклів масиву та найбільших залишкових елементів.

Рішення

Ми можемо виконати нескінченну кількість обмінів, що також означає (зміна порядку), оптимальний вибір - відсортувати масив у порядку спадання, і ми застосовуємо властивості циклів, встановлюючи $k$ до k \bmod n з позицій $m$ до m+k-1, ми додаємо найбільше число до його позиції, тобто, [найбільше, менше, ще менше, ..., найменше], нарешті, ми додаємо залишок до будь-якої позиції, оскільки це не вплине на вибрану область.

Складність O(n \log n) через використання карт.

for _ in range(int(input())):
    n, m, k = map(int, input().split())
    arr = list(map(int, input().split()))
    a = sorted(arr, reverse=True)
    r = k % n
    c = [None] * n
    for i in range(r):
        pos = (m - 1 + i) % n
        c[pos] = a[i]
    mp = {}
    for x in arr:
        mp[x] = mp.get(x, 0) + 1
    for i in range(r):
        mp[a[i]] -= 1
        if mp[a[i]] == 0:
            del mp[a[i]]
    rem = []
    for x, cnt in mp.items():
        rem.extend([x] * cnt)
    it = iter(rem)
    for i in range(n):
        if c[i] is None:
            c[i] = next(it)
    print(*c)