2110C.md (2481B)
1 Source: https://codeforces.com/problemset/problem/2110/C 2 3 C. Racing 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 In 2077, a sport called hobby-droning is gaining popularity among robots. 22 23 You already have a drone, and you want to win. For this, your drone needs to fly through a course with $n$ obstacles. 24 25 The $i$-th obstacle is defined by two numbers $l_i, r_i$. Let the height of your drone at the $i$-th obstacle be $h_i$. Then the drone passes through this obstacle if $l_i \le h_i \le r_i$. Initially, the drone is on the ground, meaning $h_0 = 0$. 26 27 The flight program for the drone is represented by an array $d_1, d_2, \ldots, d_n$, where $h_{i} - h_{i-1} = d_i$, and $0 \leq d_i \leq 1$. This means that your drone either does not change height between obstacles or rises by $1$. You already have a flight program, but some $d_i$ in it are unknown and marked as $-1$. Replace the unknown $d_i$ with numbers $0$ and $1$ to create a flight program that passes through the entire obstacle course, or report that it is impossible. 28 29 Input 30 31 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. 32 33 In the first line of each test case, an integer $n$ ($1 \le n \le 2 \cdot 10^5)$ is given — the size of the array $d$. 34 35 In the second line of each test case, there are $n$ integers $d_1, d_2, \ldots, d_n$ ($-1 \leq d_i \leq 1$) — the elements of the array $d$. $d_i = -1$ means that this $d_i$ is unknown to you. 36 37 Next, there are $n$ lines containing $2$ integers $l_i,r_i$ ($0\leq l_i\leq r_i\leq n$) — descriptions of the obstacles. 38 39 It is guaranteed that the sum of $n$ across all test cases does not exceed $2\cdot 10^5$. 40 41 Output 42 43 For each test case, output $n$ integers $d_1,d_2,\ldots,d_n$, if it is possible to correctly restore the array $d$, or $-1$ if it is not possible. 44 45 Example 46 47 Input 48 49 ``` 50 5 51 52 4 53 54 0 -1 -1 1 55 56 0 4 57 58 1 2 59 60 2 4 61 62 1 4 63 64 3 65 66 0 -1 -1 67 68 0 1 69 70 2 2 71 72 0 3 73 74 2 75 76 -1 -1 77 78 0 0 79 80 2 2 81 82 8 83 84 -1 -1 1 -1 -1 0 0 -1 85 86 0 0 87 88 0 1 89 90 0 2 91 92 0 2 93 94 1 3 95 96 0 4 97 98 2 5 99 100 4 5 101 102 1 103 104 0 105 106 1 1 107 ``` 108 109 Output 110 111 ``` 112 0 1 1 1 113 -1 114 -1 115 0 1 1 0 1 0 0 1 116 -1 117 ``` 118 119 Note 120 121 In the first test case, one possible answer is $d=[0,1,1,1]$. The array $h$ will be $[0,0+1,0+1+1,0+1+1+1]=[0,1,2,3]$. This array meets the conditions of the problem. 122 123 In the second test case, it can be proven that there is no suitable array $d$, so the answer is $-1$.