Məni Yuxudan Oyan#12315

Məni Yuxudan Oyan (Həll təhlili)

Problem Müəllifi:	Hasan Saleh (MathModel)
Hazırlayan:	Hasan Saleh (MathModel)
Redaktə edən:	Hasan Saleh (MathModel)

Həll

$p$ -ni ${1, 2, \dots, n}$ \{1,2,\dots,n\} dəstinin bir permutasiya olaraq götürək. Şərt

\forall i \in [1, n - k + 1] (j = 0 \sum k - 1 p_{i + j}) mod 2 = 1

\forall i\in[1,n-k+1]\quad \Big(\sum_{j=0}^{k-1} p_{i+j}\Big)\bmod 2 = 1

yalnız elementlərin cütlüyündən asılıdır, çünki cüt ədədlər $2$ -yə modulu $0$ verir və tək ədədlər $1$ verir.

Uzunluğu $n$ olan ikili bir massiv $s$ təyin edin:

s_{i} = p_{i} mod 2 \in {0, 1} .

s_i = p_i \bmod 2 \in \{0,1\}.

Onda şərt belə olur:

\forall i \in [1, n - k + 1] j = 0 \sum k - 1 s_{i + j} \equiv 1 (mod 2) .

\forall i\in[1,n-k+1]\quad \sum_{j=0}^{k-1} s_{i+j} \equiv 1 \pmod 2.

Beləliklə, $s$ -nin hər uzunluğu $k$ olan pəncərəsində tək sayda $1$ olmalıdır.

Əsas xüsusiyyət: dövriyyət

Tutaq ki,

S_{i} = j = 0 \sum k - 1 s_{i + j} (mod 2) .

S_i=\sum_{j=0}^{k-1}s_{i+j}\pmod 2.

Biz $S_{i} = 1$ S_i=1 olmasını istəyirik, bütün etibarlı $i$ üçün. Ardıcıllıq pəncərələrini müqayisə edək:

S_{i + 1} \equiv S_{i} - s_{i} + s_{i + k} (mod 2) .

S_{i+1} \equiv S_i - s_i + s_{i+k}\pmod 2.

Çünki $S_{i} = S_{i + 1} = 1$ S_i=S_{i+1}=1, biz alırıq

- s_{i} + s_{i + k} \equiv 0 (mod 2) \Rightarrow s_{i + k} = s_{i} .

-s_i+s_{i+k}\equiv 0 \pmod 2 \;\Rightarrow\; s_{i+k}=s_i.

Beləliklə, $s$ $k$ -dövridir. Buna görə də, $s$ tam olaraq uzunluğu $k$ olan bir naxış $b$ ilə müəyyən edilir:

b_{0}, b_{1}, \dots, b_{k - 1}, s_{i} = b_{(i - 1) mod k} .

b_0,b_1,\dots,b_{k-1},\quad s_i=b_{(i-1)\bmod k}.

Tutaq ki, $t = \sum_{j = 0}^{k - 1} b_{j}$ t=\sum_{j=0}^{k-1} b_j bir dövr içində $1$ -lərin sayıdır. Hər uzunluğu $k$ olan pəncərənin cəmi tam olaraq $t$ -dir, buna görə də şərt yalnız:

t təkdir.

Tək sayıların uyğunluğu

Permutasiya içində tək dəyərlərin sayı sabitdir:

O = # {1 \leq x \leq n : x tək} = ⌈ \frac{n}{2} ⌉ = \frac{n + 1}{2} .

O=\#\{1\le x\le n: x \text{ tək}\}=\Big\lceil\frac{n}{2}\Big\rceil=\frac{n+1}{2}.

Beləliklə, $s$ -ni tam olaraq $O$ ədəd $1$ ilə qurmalıyıq.

$n = q k + r$ n=qk+r yazın, burada $0 \leq r < k$ 0\le r<k. $k$ -dövrü olan string aşağıdakılardan ibarətdir:

$q \cdot t$ q\cdot t ədəd $1$ $q$ tam dövründən,
üstəlik $x$ ədəd $1$ naxışın ilk $r$ mövqesindən, burada $x = \sum_{j = 0}^{r - 1} b_{j}$ x=\sum_{j=0}^{r-1} b_j.

Beləliklə, bizə lazım olan:

q \cdot t + x = O .

q\cdot t + x = O.

Verilmiş $t$ üçün, $x = O - q \cdot t$ x=O-q\cdot t olur. İndi yalnız $x$ -in ilk $r$ mövqedə tam olaraq $t$ ədəd $1$ olan bir naxışın olub-olmadığını yoxlamaq lazımdır.

Mümkün aralıq $x$ üçün

Biz $k$ mövqedən $t$ ədəd $1$ seçirik; ilk $r$ mövqelər prefiksdir.

Prefiksdə maksimum $1$ sayı: $min (r, t)$ \min(r,t).
Prefiksdə minimum $1$ sayı: əgər mümkün qədər çox $1$ -i prefikdən kənarda yerləşdirsək (oradakı $k - r$ k-r mövqelər var), onda ən azı $t - (k - r)$ t-(k-r) ədəd $1$ prefikdə olmalıdır, beləliklə:
$max (0, t - (k - r)) .$
\max(0,\,t-(k-r)).

Beləliklə, verilmiş tək $t$ üçün, mümkünlük:

max (0, t - (k - r)) \leq x \leq min (r, t) .

\max(0,\,t-(k-r)) \le x \le \min(r,t).

Biz $t$ -ni $1, 3, 5, \dots, k$ 1,3,5,\dots,k tək ədədlərdən sınayırıq və ilk mümkün olanı götürürük. Əgər heç biri işləmir, cavab $- 1$ -dir.

Naxış $b$ -ni qurmaq

$(t, x)$ seçdikdən sonra:

Prefiks mövqelərində $0, 1, \dots, x - 1$ 0,1,\dots,x-1 $x$ ədəd $1$ yerləşdirin (beləliklə prefiks tam olaraq $x$ ədəd $1$ -ə malikdir).
Qalan $t - x$ t-x ədəd $1$ prefiksdən kənarda yerləşdirilməlidir (indeks $r, \dots, k - 1$ r,\dots,k-1) prefiks sayını dəyişməmək üçün.

Permutasiya qurmaq

İki siyahı hazırlayın:

artan sırada bütün tək ədədlər,
artan sırada bütün cüt ədədlər.

İndeks $i = 0.. n - 1$ i=0..n-1 üçün:

əgər $b [i mod k] = 1$ b[i\bmod k]=1 isə, növbəti tək ədədi yerləşdirin,
əks halda növbəti cüt ədədi yerləşdirin.

Bu, bir permutasiya yaradır (hər ədəd bir dəfə istifadə olunur) və quruluşuna görə cütlük naxışı $k$ -dövridir, beləliklə, hər uzunluğu $k$ olan pəncərə cəmi təkdir.

Komplekslik

Hər test üçün, biz $k$ dəyərini $2$ addım ilə sınayırıq, yəni $O (k)$ , və permutasiyanı $O (n)$ -də qururuq. Verilmiş $\sum n \leq 1 0^{6}$ \sum n\le 10^6, ümumi vaxt xətti olur.

İstinad kodu (Python)

for _ in range(int(input())):
    n,k=map(int,input().split())
    O=(n+1)//2
    q,r=divmod(n,k)

    t=x=-1
    for T in range(1,k+1,2):
        X=O-q*T
        if X<0: continue
        if max(0,T-(k-r))<=X<=min(r,T):
            t,x=T,X
            break
    if t<0:
        print(-1)
        continue

    b=[0]*k
    for i in range(x): b[i]=1
    y=t-x
    for i in range(r,k):
        if y==0: break
        b[i]=1; y-=1

    odds=list(range(1,n+1,2))
    evens=list(range(2,n+1,2))
    oi=ei=0
    ans=[]
    for i in range(n):
        if b[i%k]:
            ans.append(odds[oi]); oi+=1
        else:
            ans.append(evens[ei]); ei+=1
    print(*ans)

Python