codeforces-scrape

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

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