Permutation signée#12211

Permutation signée (Corrigé)

Auteur du problème:	Hasan Saleh (MathModel)
Préparé par:	Hasan Saleh (MathModel)
Édité par:	Hasan Saleh (MathModel)

Remarquez que la somme maximale de la permutation est la permutation elle-même sans rien faire, qui est

S = 1 + 2 + 3 + ... + n = \frac{n ( n + 1 )}{2}

\displaystyle S=1+2+3+...+n=\frac{n(n+1)}{2}

négatif d'un certain élément $x$ de $p$ signifie que $S \to S - 2 x$ S \rightarrow S-2x, cela s'applique également pour la somme d'un sous-ensemble de n'importe quelle longueur $m$ , ainsi nous avons une condition suffisante pour qu'une permutation existe réellement :

[S mod 2 = k mod 2]

[S \bmod 2 = k \bmod 2]

Ainsi, nous pouvons obtenir la somme du sous-ensemble des nombres négatifs $X = \frac{S - k}{2}$ X=\frac{S-k}{2}. Nous pouvons limiter la somme du sous-ensemble, qui est au moins

1 + 2 + 3 + ... + m = \frac{m ( m + 1 )}{2}

1+2+3+...+m=\frac{m(m+1)}{2}

, et au maximum $m$ entiers à partir du plus élevé

m + (n - 1) + (n - 2) + ... + (n - m + 1) = S - \frac{( n - m ) ( n - m + 1 )}{2}

m+(n-1)+(n-2)+...+(n-m+1)=S-\frac{(n-m)(n-m+1)}{2}

Si $X$ n'est pas limité dans cette plage, alors il est évident qu'une telle permutation n'existe pas.

Enfin, nous pouvons choisir des nombres à rendre négatifs de manière gourmande, afin que nous ayons toujours un champ pour jouer avec des entiers lors du prochain mouvement.

Solution

for _ in range(int(input())):
    n,m,k=map(int,input().split())
    S=n*(n+1)//2
    if (S-k)&1 or k>S:
        print(-1); continue
    X=(S-k)//2
    lo=m*(m+1)//2
    hi=S-(n-m)*(n-m+1)//2
    if X<lo or X>hi:
        print(-1); continue
    neg=[False]*(n+1)
    rem=m; target=X
    for i in range(n,0,-1):
        if rem==0: break
        if target>=i and target-i>=(rem-1)*rem//2:
            neg[i]=True
            target-=i
            rem-=1
    if rem or target:
        print(-1); continue
    print(*(-i if neg[i] else i for i in range(1,n+1)))

Complexité $O (n)$