codeforces-scrape

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

1253B.md (3799B)


      1 Source: https://codeforces.com/problemset/problem/1253/B
      2 
      3 B. Silly Mistake
      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 The Central Company has an office with a sophisticated security system. There are $10^6$ employees, numbered from $1$ to $10^6$.
     22 
     23 The security system logs entrances and departures. The entrance of the $i$-th employee is denoted by the integer $i$, while the departure of the $i$-th employee is denoted by the integer $-i$.
     24 
     25 The company has some strict rules about access to its office:
     26 
     27 * An employee can enter the office at most once per day.
     28 * He obviously can't leave the office if he didn't enter it earlier that day.
     29 * In the beginning and at the end of every day, the office is empty (employees can't stay at night). It may also be empty at any moment of the day.
     30 
     31 Any array of events satisfying these conditions is called a valid day.
     32 
     33 Some examples of valid or invalid days:
     34 
     35 * $[1, 7, -7, 3, -1, -3]$ is a valid day ($1$ enters, $7$ enters, $7$ leaves, $3$ enters, $1$ leaves, $3$ leaves).
     36 * $[2, -2, 3, -3]$ is also a valid day.
     37 * $[2, 5, -5, 5, -5, -2]$ is not a valid day, because $5$ entered the office twice during the same day.
     38 * $[-4, 4]$ is not a valid day, because $4$ left the office without being in it.
     39 * $[4]$ is not a valid day, because $4$ entered the office and didn't leave it before the end of the day.
     40 
     41 There are $n$ events $a_1, a_2, \ldots, a_n$, in the order they occurred. This array corresponds to one or more consecutive days. The system administrator erased the dates of events by mistake, but he didn't change the order of the events.
     42 
     43 You must partition (to cut) the array $a$ of events into contiguous subarrays, which must represent non-empty valid days (or say that it's impossible). Each array element should belong to exactly one contiguous subarray of a partition. Each contiguous subarray of a partition should be a valid day.
     44 
     45 For example, if $n=8$ and $a=[1, -1, 1, 2, -1, -2, 3, -3]$ then he can partition it into two contiguous subarrays which are valid days: $a = [1, -1~ \boldsymbol{|}~ 1, 2, -1, -2, 3, -3]$.
     46 
     47 Help the administrator to partition the given array $a$ in the required way or report that it is impossible to do. Find any required partition, you should not minimize or maximize the number of parts.
     48 
     49 Input
     50 
     51 The first line contains a single integer $n$ ($1 \le n \le 10^5$).
     52 
     53 The second line contains $n$ integers $a_1, a_2, \ldots, a_n$ ($-10^6 \le a_i \le 10^6$ and $a_i \neq 0$).
     54 
     55 Output
     56 
     57 If there is no valid partition, print $-1$. Otherwise, print any valid partition in the following format:
     58 
     59 * On the first line print the number $d$ of days ($1 \le d \le n$).
     60 * On the second line, print $d$ integers $c_1, c_2, \ldots, c_d$ ($1 \le c_i \le n$ and $c_1 + c_2 + \ldots + c_d = n$), where $c_i$ is the number of events in the $i$-th day.
     61 
     62 If there are many valid solutions, you can print any of them. You don't have to minimize nor maximize the number of days.
     63 
     64 Examples
     65 
     66 Input
     67 
     68 ```
     69 6
     70 1 7 -7 3 -1 -3
     71 ```
     72 
     73 Output
     74 
     75 ```
     76 1
     77 6
     78 ```
     79 
     80 Input
     81 
     82 ```
     83 8
     84 1 -1 1 2 -1 -2 3 -3
     85 ```
     86 
     87 Output
     88 
     89 ```
     90 2
     91 2 6
     92 ```
     93 
     94 Input
     95 
     96 ```
     97 6
     98 2 5 -5 5 -5 -2
     99 ```
    100 
    101 Output
    102 
    103 ```
    104 -1
    105 ```
    106 
    107 Input
    108 
    109 ```
    110 3
    111 -8 1 1
    112 ```
    113 
    114 Output
    115 
    116 ```
    117 -1
    118 ```
    119 
    120 Note
    121 
    122 In the first example, the whole array is a valid day.
    123 
    124 In the second example, one possible valid solution is to split the array into $[1, -1]$ and $[1, 2, -1, -2, 3, -3]$ ($d = 2$ and $c = [2, 6]$). The only other valid solution would be to split the array into $[1, -1]$, $[1, 2, -1, -2]$ and $[3, -3]$ ($d = 3$ and $c = [2, 4, 2]$). Both solutions are accepted.
    125 
    126 In the third and fourth examples, we can prove that there exists no valid solution. Please note that the array given in input is not guaranteed to represent a coherent set of events.