codeforces-scrape

Codeforces scraped problems and editorials
git clone git://git.laack.co/codeforces-scrape.git
Log | Files | Refs | README

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  ![](https://espresso.codeforces.com/b453d675ee6e4014cba1e05c4b6472ad908f0aa4.png) 
     70 
     71 The first line contains the element numbers, and the second line contains all the shifts of the desired permutation.