codeforces-scrape

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

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$.