1822D.md (1507B)
1 Source: https://codeforces.com/problemset/problem/1822/D 2 3 D. Super-Permutation 4 5 time limit per test 6 7 2 seconds 8 9 memory limit per test 10 11 256 megabytes 12 13 input 14 15 standard input 16 17 output 18 19 standard output 20 21 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. 22 23 Given a permutation $a$, we construct an array $b$, where $b_i = (a_1 + a_2 +~\dots~+ a_i) \bmod n$. 24 25 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$. 26 27 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$. 28 29 Input 30 31 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. 32 33 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. 34 35 The sum of $n$ over all test cases does not exceed $2 \cdot 10^5$. 36 37 Output 38 39 For each test case, output in a separate line: 40 41 * $n$ integers — a super-permutation of length $n$, if it exists. 42 * $-1$, otherwise. 43 44 If there are several suitable permutations, output any of them. 45 46 Example 47 48 Input 49 50 ``` 51 4 52 53 1 54 55 2 56 57 3 58 59 6 60 ``` 61 62 Output 63 64 ``` 65 1 66 2 1 67 -1 68 6 5 2 3 4 1 69 ```