Permutación con signo#12211

Permutación con signo (Editorial)

Autor del problema:	Hasan Saleh (MathModel)
Preparado por:	Hasan Saleh (MathModel)
Editado por:	Hasan Saleh (MathModel)

Ten en cuenta que la suma máxima de la permutación es la permutación misma sin hacer nada, que es

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

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

negando algún elemento $x$ de $p$ , lo que significa que $S \to S - 2 x$ S \rightarrow S-2x, esto también se aplica a la suma de algún subconjunto de cualquier longitud $m$ , por lo tanto, tenemos una condición suficiente para que una permutación realmente exista:

[S mod 2 = k mod 2]

[S \bmod 2 = k \bmod 2]

Así, podemos obtener la suma del subconjunto de números negados como $X = \frac{S - k}{2}$ X=\frac{S-k}{2}. Podemos acotar la suma del subconjunto, que es al menos

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

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

, y como máximo $m$ enteros desde el más alto

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$ no está acotado en ese rango, entonces es obvio que tal permutación no existe.

Finalmente, podemos elegir números para negar codiciosamente, de modo que siempre tengamos un campo para jugar con enteros en el siguiente movimiento.

Solución

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)))

Complejidad $O (n)$