codeforces-scrape

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

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