Sacrifice (Corrigé)

Conseils :

1) Notez que tout nombre d'échanges est équivalent à permuter le tableau en n'importe quel tableau.

2) La valeur de $m$ n'a pas d'importance dans la valeur réelle.

3) La meilleure façon est de trier le tableau par ordre décroissant et de sélectionner des entiers en fonction de cela.

4) Vérification pour le problème - vérification des cycles de tableau complets et des plus grands éléments restants.

Solution

Nous pouvons effectuer un nombre infini d'échanges, ce qui signifie également (changer l'ordre), le choix optimal est de trier le tableau par ordre décroissant, et nous appliquons les propriétés des cycles, en définissant $k$ à k \bmod n des positions $m$ à m+k-1, nous ajoutons le plus grand nombre à sa position, c'est-à-dire, [plus grand, plus petit, encore plus petit, ..., le plus petit], enfin, nous ajoutons le reste à n'importe quelle position puisque cela n'affectera pas la zone sélectionnée.

Complexité O(n \log n) en raison de l'utilisation de cartes.

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)