2130B.md (2459B)
1 Source: https://codeforces.com/problemset/problem/2130/B 2 3 B. Pathless 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 There is an array $a_1, a_2, \ldots, a_n$ consisting of values $0$, $1$, and $2$, and an integer $s$. It is guaranteed that $a_1, a_2, \ldots, a_n$ contains at least one $0$, one $1$, and one $2$. 22 23 Alice wants to start from index $1$ and perform steps of length $1$ to the right or to the left, and reach index $n$ at the end. While Alice moves, she calculates the sum of the values she is visiting, and she wants the sum to be exactly $s$. 24 25 Formally, Alice wants to find a sequence $[i_1, i_2, \ldots, i_m]$ of indices, such that: 26 27 * $i_1 = 1$, $i_m = n$. 28 * $1 \leq i_j \leq n$ for all $1 \le j \le m$. 29 * $|i_{j} - i_{j+1}| = 1$ for all $1 \leq j \lt m$. 30 * $a_{i_1} + a_{i_2} + \ldots + a_{i_m} = s$. 31 32 However, Bob wants to rearrange $a_1, a_2, \ldots, a_n$ to prevent Alice from achieving her target. Determine whether it is possible to rearrange $a_1, a_2, \ldots, a_n$ such that Alice cannot find her target sequence (even if Alice is smart enough). If it is possible, you also need to output the rearranged array $a_1, a_2, \ldots, a_n$. 33 34 Input 35 36 Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 10^3$). The description of the test cases follows. 37 38 The first line of each test case contains two integers $n$ and $s$ ($3 \le n \le 50$, $0 \le s \le 1000$). 39 40 The second line of each test case contains $n$ integers $a_1, a_2, \ldots, a_n$ ($0 \le a_i \le 2$). 41 42 It is guaranteed that $a$ contains at least one $0$, one $1$, and one $2$. 43 44 Output 45 46 For each test case, if it is possible to rearrange $a$ such that Alice cannot find her target sequence, output $n$ integers — such rearrangement of $a$. Otherwise, output $-1$ instead. 47 48 Example 49 50 Input 51 52 ``` 53 6 54 55 3 2 56 57 0 1 2 58 59 3 3 60 61 0 1 2 62 63 3 6 64 65 0 1 2 66 67 3 4 68 69 0 1 2 70 71 3 10 72 73 0 1 2 74 75 5 1000 76 77 2 0 1 1 2 78 ``` 79 80 Output 81 82 ``` 83 0 1 2 84 -1 85 -1 86 0 2 1 87 -1 88 -1 89 ``` 90 91 Note 92 93 In the first test case, any rearrangement of $a$ can prevent Alice from achieving her target. 94 95 In the second test case, regardless of rearranging $a$, Alice can always find the sequence $[1,2,3]$ as her target sequence. 96 97 In the third test case,there is no rearrangement of $a$ that can prevent Alice from achieving her target. For example, for $a=[0,2,1]$, Alice can find the sequence $[1,2,3,2,3]$ as her target sequence.