Super-Permutation (Codeforces 1822D)
Tags: Math, constructive algorithms

A permutation is a sequence $$$n$$$ integers, where each integer from $$$1$$$ to $$$n$$$ appears exactly once. For example, $$$[1]$$$, $$$[3,5,2,1,4]$$$, $$$[1,3,2]$$$ are permutations, while $$$[2,3,2]$$$, $$$[4,3,1]$$$, $$$[0]$$$ are not.Given a permutation $$$a$$$, we construct an array $$$b$$$, where $$$b_i = (a_1 + a_2 +~\dots~+ a_i) \bmod n$$$.A permutation of numbers $$$[a_1, a_2, \dots, a_n]$$$ is called a super-permutation if $$$[b_1 + 1, b_2 + 1, \dots, b_n + 1]$$$ is also a permutation of length $$$n$$$.Grisha became interested whether a super-permutation of length $$$n$$$ exists. Help him solve this non-trivial problem. Output any super-permutation of length $$$n$$$, if it exists. Otherwise, output $$$-1$$$.

Input: The first line contains a single integer $$$t$$$ ($$$1 \le t \le 10^4$$$) — the number of test cases. The description of the test cases follows.Each test case consists of a single line containing one integer $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$) — the length of the desired permutation.The sum of $$$n$$$ over all test cases does not exceed $$$2 \cdot 10^5$$$.

Output: For each test case, output in a separate line:  $$$n$$$ integers — a super-permutation of length $$$n$$$, if it exists.  $$$-1$$$, otherwise. If there are several suitable permutations, output any of them.


Sample Inputs:
4
1
2
3
6

Sample Outputs:
1
2 1
-1
6 5 2 3 4 1

Solution (Python):
import sys, threading, bisect, heapq, math, copy
from heapq import heappush, heappop
from functools import cmp_to_key as ctk, lru_cache
from collections import defaultdict, deque
readline = sys.stdin.readline
read = lambda : list(map(int, readline().split()))
readstr = lambda : readline().rstrip()
alloc = lambda dfv, *s: len(s) != 1 and [alloc(dfv, *s[1:]) for _ in range(int(s[0]))] or [dfv] * int(s[0])
show = lambda arr: print(' '.join(map(str, arr)))

def main():
    INF = float('inf')
    MOD = 10 ** 9 + 7
    for _ in range(int(input())):
        (n,) = read()
        if n > 1 and n % 2:
            print(-1)
        else:
            show([n - i if i % 2 == 0 else i for i in range(n)])
main()

Solution (Python):
import sys
from collections import defaultdict as dd
from sys import maxsize
import math
input = sys.stdin.readline

def inpt():
    return int(input())

def inpl():
    return list(map(int, input().split()))

def inps():
    s = input()
    return list(s[:len(s) - 1])

def main():
    n = inpt()
    if n == 1:
        return 1
    elif n % 2:
        return -1
    ans = []
    for i in range(0, n, 2):
        ans.append(n - i)
        ans.append(i + 1)
    return ' '.join(map(str, ans))
for _ in range(inpt()):
    print(main())

Solution (Python):
def f(n):
    if n == 1:
        return '1'
    elif n > 1 and n % 2 != 0:
        return '-1'
    a = []
    for i in range(n):
        if i % 2 == 1:
            a.append(i)
        else:
            a.append(n - i)
    return ' '.join((str(i) for i in a))
t = int(input())
for _ in range(t):
    n = int(input())
    res = f(n)
    print(res)