Wake Me Up (Editorial)

Solution

Let $p$ be a permutation of \{1,2,\dots,n\}. The condition

depends only on the parities of the elements, since even numbers contribute $0$ modulo $2$ and odd numbers contribute $1$.

Define a binary array $s$ of length $n$:

Then the condition becomes:

So every length-$k$ window of $s$ has an odd number of ones.

Key property: periodicity

Let

We need S_i=1 for all valid $i$. Compare consecutive windows:

Since S_i=S_{i+1}=1, we get

Hence $s$ is $k$-periodic. Therefore, $s$ is fully determined by a pattern $b$ of length $k$:

Let t=\sum_{j=0}^{k-1} b_j be the number of ones in one period. The sum of any length-$k$ window is exactly $t$, so the condition holds iff:

Matching the number of odds

In the permutation, the number of odd values is fixed:

So we must construct $s$ with exactly $O$ ones.

Write n=qk+r with 0\le r<k. The $k$-periodic string contains:

• q\cdot t ones from the $q$ full periods,

• plus $x$ ones from the first $r$ positions of the pattern, where x=\sum_{j=0}^{r-1} b_j.

So we need:

Given $t$, we have x=O-q\cdot t. Now we only need to check whether a pattern with exactly $t$ ones can have exactly $x$ ones inside its first $r$ positions.

Feasible range for $x$

We choose $t$ ones among $k$ positions; the first $r$ positions are a prefix.

• Maximum ones in the prefix: \min(r,t).

• Minimum ones in the prefix: if we put as many ones as possible outside the prefix (there are k-r positions), then at least t-(k-r) ones must be inside, so:

  \max(0,\,t-(k-r)).

Therefore, for a given odd $t$, feasibility is:

We try odd t\in\{1,3,5,\dots,k\} and take the first feasible one. If none works, answer is $-1$.

Constructing the pattern $b$

After choosing $(t,x)$:

• Put $x$ ones in the prefix positions 0,1,\dots,x-1 (so the prefix has exactly $x$ ones).

• The remaining t-x ones must be placed outside the prefix (indices r,\dots,k-1) to keep the prefix count unchanged.

Constructing the permutation

Prepare two lists:

• all odd numbers in increasing order,

• all even numbers in increasing order.

For position i=0..n-1:

• if b[i\bmod k]=1, place the next odd,

• else place the next even.

This produces a permutation (each number used once), and by construction the parity pattern is $k$-periodic with an odd period-sum, so every length-$k$ window sum is odd.

Complexity

For each test, we try at most $k$ values of $t$ with step $2$, i.e. $O(k)$, and build the permutation in $O(n)$. Given \sum n\le 10^6, total time is linear.

Reference code (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)