Перестановка зі знаком#12211

Перестановка зі знаком (Розбір)

Автор проблеми:	Хасан Салех (MathModel)
Підготовлено:	Хасан Салех (MathModel)
Редагував:	Хасан Салех (MathModel)

Зверніть увагу, що максимальна сума перестановки - це сама перестановка без жодних змін, яка є

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

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

негування деякого елемента $x$ з $p$ означає, що $S \to S - 2 x$ S \rightarrow S-2x, це також застосовується до суми деякої підмножини будь-якої довжини $m$ , таким чином, у нас є достатня умова для того, щоб перестановка насправді існувала:

[S mod 2 = k mod 2]

[S \bmod 2 = k \bmod 2]

Таким чином, ми можемо отримати суму підмножини від'ємних чисел $X = \frac{S - k}{2}$ X=\frac{S-k}{2}, ми можемо обмежити суму підмножини, яка щонайменше

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

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

, і в найгіршому випадку $m$ цілих чисел з найбільших

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}

Якщо $X$ не обмежено в цьому діапазоні, то очевидно, що така перестановка не існує.

Нарешті, ми можемо вибрати числа для негативу жадібно, так що у нас завжди є поле для маневру з цілими числами в наступному ході.

Рішення

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

Складність $O (n)$