Qurbongoh (Editorial)

Tavsiyalar:

1) Har qanday almashuvlar soni massivni istalgan massivga permutatsiya qilish bilan tengdir.

2) $m$ ning qiymati haqiqiy qiymatda ahamiyatga ega emas.

3) Optimal yo'l - massivni kamayish tartibida saralash va shu asosda butun sonlarni tanlash.

4) Muammoni tekshirish - to'liq massiv aylanishlarini va eng katta qolgan elementlarni tekshirish.

Yecha

Biz cheksiz sonli almashuvlarni amalga oshirishimiz mumkin, bu ham (tartibni o'zgartirish) deganidir, optimal tanlov - massivni kamayish tartibida saralash va biz aylanishlar xususiyatlarini qo'llaymiz, $k$ ni k \bmod n ga belgilaymiz, $m$ dan m+k-1 gacha, eng katta sonni o'z pozitsiyasiga qo'shamiz, ya'ni, [eng katta, kichikroq, hatto kichikroq, ..., eng kichik], oxirida, qolganini istalgan pozitsiyaga qo'shamiz, chunki bu tanlangan maydonga ta'sir qilmaydi.

Murakkablik O(n \log n) xaritalardan foydalanish tufayli.

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)