codeforces-scrape

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

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 ```