2031C.md (2579B)
1 Source: https://codeforces.com/problemset/problem/2031/C 2 3 C. Penchick and BBQ Buns 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 Penchick loves two things: square numbers and Hong Kong-style BBQ buns! For his birthday, Kohane wants to combine them with a gift: $n$ BBQ buns arranged from left to right. There are $10^6$ available fillings of BBQ buns, numbered from $1$ to $10^6$. To ensure that Penchick would love this gift, Kohane has a few goals: 22 23 * No filling is used exactly once; that is, each filling must either not appear at all or appear at least twice. 24 * For any two buns $i$ and $j$ that have the same filling, the distance between them, which is $|i-j|$, must be a perfect square$^{\text{∗}}$. 25 26 Help Kohane find a valid way to choose the filling of the buns, or determine if it is impossible to satisfy her goals! If there are multiple solutions, print any of them. 27 28 $^{\text{∗}}$A positive integer $x$ is a perfect square if there exists a positive integer $y$ such that $x = y^2$. For example, $49$ and $1$ are perfect squares because $49 = 7^2$ and $1 = 1^2$ respectively. On the other hand, $5$ is not a perfect square as no integer squared equals $5$ 29 30 Input 31 32 Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 2\cdot 10^5$). The description of the test cases follows. 33 34 The only line of each test case contains a single integer $n$ ($1\le n\le 2\cdot 10^5$) — the number of BBQ buns. 35 36 It is guaranteed that the sum of $n$ over all test cases does not exceed $2 \cdot 10^5$. 37 38 Output 39 40 For each test case, if no valid choice of fillings exists, output $-1$. Otherwise, output $n$ integers, where the $i$-th integer represents the filling of the $i$-th BBQ bun. If there are multiple solutions, print any of them. 41 42 Example 43 44 Input 45 46 ``` 47 2 48 49 3 50 51 12 52 ``` 53 54 Output 55 56 ``` 57 -1 58 1 2 3 6 10 2 7 6 10 1 7 3 59 ``` 60 61 Note 62 63 In the first test case, the choice of fillings "1 1 1" is not allowed because buns $1$ and $3$ have the same filling, but are distance $2$ apart, which is not a perfect square. The choice of fillings "1 1 2" is also not allowed as filling $2$ is only used once. 64 65 In the second test case, the solution is valid because no filling is used exactly once, and any two buns with the same filling are spaced at a distance equal to a perfect square. For example, buns $1$ and $10$ both have filling $1$ and are spaced at a distance of $9=3^2$. Similarly, buns $5$ and $9$ both have filling $10$ and are spaced at a distance of $4=2^2$.