← 返回题目列表

AtCoder · abc333_e

H. 高桥任务

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

分数: 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