Takahashi Quest

题目描述

Takahashi 将开始一次冒险。 在冒险过程中，会发生 $N$ 个事件。 第 $i$ 个事件 $(1\leq i\leq N)$ 由一个整数对 $(t _ i,x _ i)$ 表示 $(1\leq t _ i\leq 2,1\leq x _ i\leq N)$，具体如下：

如果 $t _ i=1$，他发现了一瓶类型为 $x _ i$ 的药水。他可以选择拾取它或丢弃它。 如果 $t _ i=2$，他遇到了一只类型为 $x _ i$ 的怪物。如果他有一瓶类型为 $x _ i$ 的药水，他可以使用一瓶来击败该怪物。如果他不击败它，他将被击败。

判断他是否可以在不被击败的情况下击败所有怪物。 如果他不能击败所有怪物，输出 $-1$。 否则，令 $K$ 为他在冒险过程中某一时刻拥有的药水数的最大值。 令 $K _ {\min}$ 为在所有不会被击败的策略中 $K$ 的最小值。 输出 $K _ {\min}$ 的值以及能够实现 $K _ {\min}$ 的 Takahashi 的行动。

输入格式

输入由标准输入提供，格式如下： $N$ $t _ 1$ $x _ 1$ $t _ 2$ $x _ 2$ $\vdots$ $t _ N$ $x _ N$

输出格式

如果 Takahashi 无法击败所有怪物，输出 $-1$。 如果可以，第一行输出 $K _ {\min}$ 的值，第二行对于每个满足 $t _ i=1$ 的 $i$（按升序），输出如果他在第 $i$ 个事件拾起所发现的药水则为 $1$，否则为 $0$，各值之间用空格分隔。 如果存在多个能够实现 $K _ {\min}$ 且能使他完成冒险的行动序列，你可以输出其中任何一个。

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

3
1 1 1 0 0 1 0 1

4
2 3
1 4
2 1
1 2

-1

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

4
1 1 1 1 1 0 1 0 0 0 0 1 1 0 1 0 1 0 0 0

提示

$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)$ 所有输入值均为整数。样例输出对应于以下行动：

按此顺序发现类型为 $2,3,1$ 的药水。全部拾取它们。 按此顺序发现类型为 $3,2$ 的药水。不拾取它们中的任何一个。 遇到一只类型为 $3$ 的怪物。使用一瓶类型为 $3$ 的药水击败它。 发现一瓶类型为 $3$ 的药水。拾取它。 发现一瓶类型为 $3$ 的药水。不拾取它。 遇到一只类型为 $3$ 的怪物。使用一瓶类型为 $3$ 的药水击败它。 发现一瓶类型为 $3$ 的药水。拾取它。 遇到一只类型为 $2$ 的怪物。使用一瓶类型为 $2$ 的药水击败它。 遇到一只类型为 $3$ 的怪物。使用一瓶类型为 $3$ 的药水击败它。 遇到一只类型为 $1$ 的怪物。使用一瓶类型为 $1$ 的药水击败它。

在这个行动序列中，$K$ 的值为 $3$。 无法在 $K\leq 2$ 的情况下避免被击败，因此所求的 $K _ {\min}$ 为 $3$。 存在多个满足 $K=3$ 且能避免被击败的行动序列；你可以输出其中任意一个。
他将在遇到的第一个怪物处必然被击败。

标签: AtCoder|abc333E

来源

AtCoder|abc333E