Sacrifice (Çözgüdiň düşündirişi)

Tips:

1) Note that any number of swaps is equivalent to permuting the array into any array.

2) The value of $m$ does not matter in the actual value.

3) The optimal way is to sort the array in descending order and select integers based on that.

4) Verification for the problem - checking full array cycles and the largest remaining elements.

Solution

We can perform an infinite number of swaps, which also means (changing the order), the optimal choice is to sort the array in descending order, and we apply the properties of cycles, setting $k$ to k \bmod n from positions $m$ to m+k-1, we add the largest number to its position, i.e., [largest, smaller, even smaller, ..., smallest], finally, we add the remainder to any position since it will not affect the selected area.

Complexity O(n \log n) due to the use of maps.

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)