2091C.md (2216B)
1 Source: https://codeforces.com/problemset/problem/2091/C 2 3 C. Combination Lock 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 At the IT Campus "NEIMARK", there are several top-secret rooms where problems for major programming competitions are developed. To enter one of these rooms, you must unlock a circular lock by selecting the correct code. This code is updated every day. 22 23 Today's code is a permutation$^{\text{∗}}$ of the numbers from $1$ to $n$, with the property that in every cyclic shift$^{\text{†}}$ of it, there is exactly one fixed point. That is, in every cyclic shift, there exists exactly one element whose value is equal to its position in the permutation. 24 25 Output any valid permutation that satisfies this condition. Keep in mind that a valid permutation might not exist, then output $-1$. 26 27 $^{\text{∗}}$A permutation is defined as a sequence of length $n$ consisting of integers from $1$ to $n$, where each number appears exactly once. For example, (2 1 3), (1), (4 3 1 2) are permutations; (1 2 2), (3), (1 3 2 5) are not. 28 29 $^{\text{†}}$A cyclic shift of an array is obtained by moving the last element to the beginning of the array. A permutation of length $n$ has exactly $n$ cyclic shifts. 30 31 Input 32 33 Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \leq t \leq 500$). The description of the test cases follows. 34 35 A single line of each test case contains a single integer $n$ ($1 \leq n \leq 2 \cdot 10^5$). 36 37 It is guaranteed that the sum of $n$ over all test cases does not exceed $2 \cdot 10^5$. 38 39 Output 40 41 For each test case, output the desired permutation. If multiple solutions exist, output any one of them. If no suitable permutations exist, output $-1$. 42 43 Example 44 45 Input 46 47 ``` 48 3 49 50 4 51 52 5 53 54 3 55 ``` 56 57 Output 58 59 ``` 60 -1 61 4 1 3 5 2 62 1 3 2 63 ``` 64 65 Note 66 67 In the second example, there is a permutation such that in each cyclic shift there is a fixed point (highlighted in dark red): 68 69  70 71 The first line contains the element numbers, and the second line contains all the shifts of the desired permutation.