2037C.md (1980B)
1 Source: https://codeforces.com/problemset/problem/2037/C 2 3 C. Superultra's Favorite 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 Superultra, a little red panda, desperately wants primogems. In his dreams, a voice tells him that he must solve the following task to obtain a lifetime supply of primogems. Help Superultra! 22 23 Construct a permutation$^{\text{∗}}$ $p$ of length $n$ such that $p_i + p_{i+1}$ is composite$^{\text{†}}$ over all $1 \leq i \leq n - 1$. If it's not possible, output $-1$. 24 25 $^{\text{∗}}$A permutation of length $n$ is an array consisting of $n$ distinct integers from $1$ to $n$ in arbitrary order. For example, $[2,3,1,5,4]$ is a permutation, but $[1,2,2]$ is not a permutation ($2$ appears twice in the array), and $[1,3,4]$ is also not a permutation ($n=3$ but there is $4$ in the array). 26 27 $^{\text{†}}$An integer $x$ is composite if it has at least one other divisor besides $1$ and $x$. For example, $4$ is composite because $2$ is a divisor. 28 29 Input 30 31 The first line contains $t$ ($1 \leq t \leq 10^4$) — the number of test cases. 32 33 Each test case contains an integer $n$ ($2 \leq n \leq 2 \cdot 10^5$) — the length of the permutation. 34 35 It is guaranteed that the sum of $n$ over all test cases does not exceed $2 \cdot 10^5$. 36 37 Output 38 39 For each test case, if it's not possible to construct $p$, output $-1$ on a new line. Otherwise, output $n$ integers $p_1, p_2, \ldots, p_n$ on a new line. 40 41 Example 42 43 Input 44 45 ``` 46 2 47 48 3 49 50 8 51 ``` 52 53 Output 54 55 ``` 56 -1 57 1 8 7 3 6 2 4 5 58 ``` 59 60 Note 61 62 In the first example, it can be shown that all permutation of size $3$ contain two adjacent elements whose sum is prime. For example, in the permutation $[2,3,1]$ the sum $2+3=5$ is prime. 63 64 In the second example, we can verify that the sample output is correct because $1+8$, $8+7$, $7+3$, $3+6$, $6+2$, $2+4$, and $4+5$ are all composite. There may be other constructions that are correct.