1713C.md (1671B)
1 Source: https://codeforces.com/problemset/problem/1713/C 2 3 C. Build Permutation 4 5 time limit per test 6 7 1 second 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 $\mathbf{0}$-indexed array $a$ of size $n$ is called good if for all valid indices $i$ ($0 \le i \le n-1$), $a_i + i$ is a perfect square$^\dagger$. 22 23 Given an integer $n$. Find a permutation$^\ddagger$ $p$ of $[0,1,2,\ldots,n-1]$ that is good or determine that no such permutation exists. 24 25 $^\dagger$ An integer $x$ is said to be a perfect square if there exists an integer $y$ such that $x = y^2$. 26 27 $^\ddagger$ An array $b$ is a permutation of an array $a$ if $b$ consists of the elements of $a$ in arbitrary order. For example, $[4,2,3,4]$ is a permutation of $[3,2,4,4]$ while $[1,2,2]$ is not a permutation of $[1,2,3]$. 28 29 Input 30 31 The first line contains a single integer $t$ ($1 \le t \le 10^4$) — the number of test cases. 32 33 The only line of each test case contains a single integer $n$ ($1 \le n \le 10^5$) — the length of the permutation $p$. 34 35 It is guaranteed that the sum of $n$ over all test cases does not exceed $10^5$. 36 37 Output 38 39 For each test case, output $n$ distinct integers $p_0, p_1, \dots, p_{n-1}$ ($0 \le p_i \le n-1$) — the permutation $p$ — if the answer exists, and $-1$ otherwise. 40 41 Example 42 43 Input 44 45 ``` 46 3 47 48 3 49 50 4 51 52 7 53 ``` 54 55 Output 56 57 ``` 58 1 0 2 59 0 3 2 1 60 1 0 2 6 5 4 3 61 ``` 62 63 Note 64 65 In the first test case, we have $n=3$. The array $p = [1, 0, 2]$ is good since $1 + 0 = 1^2$, $0 + 1 = 1^2$, and $2 + 2 = 2^2$ 66 67 In the second test case, we have $n=4$. The array $p = [0, 3, 2, 1]$ is good since $0 + 0 = 0^2$, $3 + 1 = 2^2$, $2+2 = 2^2$, and $1+3 = 2^2$.