2147B.md (2049B)
1 Source: https://codeforces.com/problemset/problem/2147/B 2 3 B. Multiple Construction 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 You are given an integer $n$. Your task is to construct an array of length $2 \cdot n$ such that: 22 23 * Each integer from $1$ to $n$ appears exactly twice in the array. 24 * For each integer $x$ ($1 \le x \le n$), the distance between the two occurrences of $x$ is a multiple of $x$. In other words, if $p_x$ and $q_x$ are the indices of the two occurrences of $x$, $| q_x - p_x |$ must be divisible by $x$. 25 26 It can be shown that a solution always exists. 27 28 Input 29 30 Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 10^4$). The description of the test cases follows. 31 32 Each of the next $t$ lines contains a single integer $n$ ($1 \le n \le 2 \cdot 10^{5}$). 33 34 It is guaranteed that the sum of $n$ over all test cases does not exceed $2 \cdot 10^{5}$. 35 36 Output 37 38 For each test case, print a line containing $2 \cdot n$ integers — the array that satisfies the given conditions. 39 40 If there are multiple valid answers, print any of them. 41 42 Example 43 44 Input 45 46 ``` 47 3 48 2 49 3 50 1 51 ``` 52 53 Output 54 55 ``` 56 1 2 1 2 57 1 3 1 2 3 2 58 1 1 59 ``` 60 61 Note 62 63 [Visualizer link](https://codeforces.com/assets/contests/2147/B_RlbLXHyL5DuDqDlx4DG1.html) 64 65 In the first test case: 66 67 * The number $1$ appears at positions $1$ and $3$: the distance is $2$, which is divisible by $1$. 68 * The number $2$ appears at positions $2$ and $4$: the distance is $2$, which is divisible by $2$. 69 70 In the second test case: 71 72 * The number $1$ appears at positions $1$ and $3$: the distance is $2$, which is divisible by $1$. 73 * The number $2$ appears at positions $4$ and $6$: the distance is $2$, which is divisible by $2$. 74 * The number $3$ appears at positions $2$ and $5$: the distance is $3$, which is divisible by $3$. 75 76 In the third test case, the two occurrences of $1$ are at positions $1$ and $2$, so the distance between them is $1$, which is a multiple of $1$.