分数: 450 点
问题陈述
高桥将踏上冒险之旅。
在冒险过程中, N 事件将会发生。 的 i第一个事件 (1\leq i\leq N) 由一对整数表示 (t _ i,x _ i) (1\leq t _ i\leq 2,1\leq x _ i\leq N) 如下:
- If t _ i=1,他找到了一瓶类型的药水 x _ i。他可以选择捡起或丢弃。
- If t _ i=2,他遇到了一只类型为 x _ i。如果他有一瓶类型的药水 x _ i,他可以用一击击败怪物。如果他不打败它,他就会被打败。
判断他能否在不被击败的情况下击败所有怪物。
如果他无法击败所有怪物,则打印 -1.
否则,让 K 是他在冒险过程中某个时刻拥有的最大药水数量。 让 K _ {\min} 是最小值 K 在所有策略中他都不会被击败。 打印值 K _ {\min} 以及高桥的行动实现了 K _ {\min}.
约束
- 1\leq N\leq2\times10^5
- 1\leq t _ i\leq2\ (1\leq i\leq N)
- 1\leq x _ i\leq N\ (1\leq i\leq N)
- 所有输入值均为整数。
输入
输入由标准输入按以下格式给出:
N t _ 1 x _ 1 t _ 2 x _ 2 \vdots t _ N x _ N
输出
如果高桥无法击败所有怪物,则打印 -1。
如果可以的话,打印出 K _ {\min} 在第一行和第二行中,对于每个 i 这样 t _ i=1 按升序,打印 1 如果他捡起了在 i第一个事件,以及 0 否则,用空格分隔。
如果多个动作序列实现 K _ {\min} 并让他在不被击败的情况下完成冒险,您可以打印其中任何一个。
示例输入 1
13 1 2 1 3 1 1 1 3 1 2 2 3 1 3 1 3 2 3 1 3 2 2 2 3 2 1
示例输出 1
3 1 1 1 0 0 1 0 1
示例输出对应于以下操作:
- 查找不同类型的药水 2,3,1 按此顺序。把它们全部捡起来。
- 查找不同类型的药水 3,2 按此顺序。不要拿起其中任何一个。
- 遇到类型-3 怪物。使用一种类型 -3 药水来击败它。
- 查找类型-3 药水。捡起来。
- 查找类型-3 药水。不要捡起它。
- 遇到类型-3 怪物。使用一种类型 -3 药水来击败它。
- 查找类型-3 药水。捡起来。
- 遇到类型-2 怪物。使用一种类型 -2 药水来击败它。
- 遇到类型-3 怪物。使用一种类型 -3 药水来击败它。
- 遇到类型-1 怪物。使用一种类型 -1 药水来击败它。
在这一系列操作中, K is 3.
没有办法避免失败 K\leq 2,所以寻求的值 K _ {\min} is 3。 有多个动作序列满足 K=3 并让他避免失败;您可以打印其中任何一个。
示例输入 2
4 2 3 1 4 2 1 1 2
示例输出 2
-1
他不可避免地会被他遇到的第一个怪物打败。
示例输入 3
30 1 25 1 2 1 10 1 18 2 18 1 11 2 11 1 21 1 6 2 2 2 10 1 11 1 24 1 11 1 3 1 2 1 18 2 25 1 8 1 10 1 11 2 18 2 10 1 10 2 2 1 24 1 10 2 10 1 25 2 6
示例输出 3
4 1 1 1 1 1 0 1 0 0 0 0 1 1 0 1 0 1 0 0 0