Kurban (Editoryal)

İpuçları:

1) Herhangi bir sayıda takas yapmanın, diziyi herhangi bir diziye permütasyon etmekle eşdeğer olduğunu unutmayın.

2) $m$ değerinin gerçek değerde bir önemi yoktur.

3) Optimal yol, diziyi azalan sırada sıralamak ve buna göre tamsayıları seçmektir.

4) Problemin doğrulaması - tam dizi döngülerini ve en büyük kalan elemanları kontrol etme.

Çözüm

Sonsuz sayıda takas yapabiliriz, bu da (sıralamayı değiştirmek) anlamına gelir, optimal seçim diziyi azalan sırada sıralamak ve döngü özelliklerini uygulamaktır, $k$'yı k \bmod n olarak ayarlayarak $m$'den m+k-1'e kadar en büyük sayıyı pozisyonuna ekleriz, yani, [en büyük, daha küçük, daha da küçük, ..., en küçük], sonunda, kalan herhangi bir pozisyona ekleriz çünkü bu seçilen alanı etkilemeyecektir.

Karmaşıklık O(n \log n) haritaların kullanılmasından dolayıdır.

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)