← 返回题目列表

Codeforces · 1253/B

B. 愚蠢的错误

中文机器翻译题面 查看原题

中央公司的办公室拥有先进的安全系统。有 $$$10^6$$$ 员工,编号从 $$$1$$$ 到 $$$10^6$$$。

安全系统记录入口和出口。第 $$$i$$$ 员工的进入由整数 $$$i$$$ 表示,而第 $$$i$$$ 员工的离开由整数 $$$-i$$$ 表示。

公司对于进入其办公室有一些严格的规定:

- 一名员工每天最多可以进入办公室一次。
- 如果他当天不早点进入办公室,他显然无法离开办公室。
- 每天开始和结束时,办公室都是空的(员工不能过夜)。它也可能在一天中的任何时刻都是空的。

满足这些条件的任何事件数组都称为有效日。

有效或无效日期的一些示例:

- $$$[1, 7, -7, 3, -1, -3]$$$ 是有效日期($$$1$$$ 进入、$$$7$$$ 进入、$$$7$$$ 离开、$$$3$$$ 进入、$$$1$$$ 离开、$$$3$$$ 离开)。
- $$$[2, -2, 3, -3]$$$ 也是有效日期。
- $$$[2, 5, -5, 5, -5, -2]$$$ 不是有效日期,因为 $$$5$$$ 在同一天内两次进入办公室。
- $$$[-4, 4]$$$ 不是有效的一天,因为 $$$4$$$ 离开了办公室但并未在办公室。
- $$$[4]$$$ 不是有效的一天,因为 $$$4$$$ 进入了办公室并且在该天结束之前没有离开。

有 $$$n$$$ 个事件 $$$a_1、a_2、\ldots、a_n$$$(按发生顺序排列)。该数组对应于连续的一天或多天。系统管理员错误地删除了事件的日期,但他没有更改事件的顺序。

您必须将事件数组 $$$a$$$ 分区(切割)为连续的子数组,这些子数组必须表示非空的有效日期(或者说这是不可能的)。每个数组元素应该恰好属于分区的一个连续子数组。分区的每个连续子数组都应该是有效的一天。

例如,如果 $$$n=8$$$ 和 $$$a=[1, -1, 1, 2, -1, -2, 3, -3]$$$ 那么他可以将其划分为两个连续的有效日期子数组: $$$a = [1, -1~ \boldsymbol{|}~ 1, 2, -1, -2, 3, -3]$$$。

帮助管理员按要求的方式对给定数组 $$$a$$$ 进行分区,否则报告不可能这样做。找到任何需要的分区,您不应该最小化或最大化部件的数量。

输入

第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 10^5$$$)。

第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \ldots, a_n$$$ ($$$-10^6 \le a_i \le 10^6$$$ 和 $$$a_i \neq 0$$$)。

输出

如果没有有效分区,则打印$$$-1$$$。否则,按以下格式打印任何有效分区:

- 在第一行打印 $$$d$$$ 天数 ($$$1 \le d \le n$$$)。
- 在第二行,打印 $$$d$$$ 整数 $$$c_1, c_2, \ldots, c_d$$$ ($$$1 \le c_i \le n$$$ 和 $$$c_1 + c_2 + \ldots + c_d = n$$$),其中 $$$c_i$$$ 是事件中的事件数$$$i$$$ 第一天。

如果有很多有效的解决方案,您可以打印其中任何一个。您不必最小化或最大化天数。

示例

输入 #1

6
1 7 -7 3 -1 -3

输出 #1

1
6

输入 #2

8
1 -1 1 2 -1 -2 3 -3

输出 #2

2
2 6

输入 #3

6
2 5 -5 5 -5 -2

输出 #3

-1

输入#4

3
-8 1 1

输出#4

-1

注意

在第一个示例中,整个数组都是有效日期。

在第二个示例中,一种可能的有效解决方案是将数组拆分为 $$$[1, -1]$$$ 和 $$$[1, 2, -1, -2, 3, -3]$$$($$$d = 2$$$ 和 $$$c = [2, 6]$$$)。唯一有效的解决方案是将数组拆分为 $$$[1, -1]$$$、$$$[1, 2, -1, -2]$$$ 和 $$$[3, -3]$$$ ($$$d = 3$$$ 和 $$$c = [2, 4, 2]$$$)。两种解决方案均被接受。

在第三个和第四个例子中,我们可以证明不存在有效的解。请注意,输入中给出的数组不能保证代表一组连贯的事件。