AT_abc333_e [ABC333E] Takahashi Quest

高桥君准备踏上冒险之旅。 在冒险过程中，将会发生 $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$ 的最小值记为 $K_{\min}$。请输出 $K_{\min}$ 的值，并输出一种能够实现 $K_{\min}$ 且高桥君不会失败的行为方案。

输入以如下格式从标准输入读入。 > $N$ > $t_1$ $x_1$ > $t_2$ $x_2$ > $\vdots$ > $t_N$ $x_N$

如果高桥君无法击退所有怪物，输出 `-1`。 如果高桥君能够击退所有怪物，第一行输出 $K_{\min}$ 的值。第二行按顺序输出所有 $t_i = 1$ 的事件，对于第 $i$ 个事件发现的药水，若拾取则输出 `1`，否则输出 `0`，用空格分隔。 若存在多种实现 $K_{\min}$ 且不会失败的行为方案，输出任意一种均可。

### 限制条件 - $1 \leq N \leq 2 \times 10^5$ - $1 \leq t_i \leq 2\ (1 \leq i \leq N)$ - $1 \leq x_i \leq N\ (1 \leq i \leq N)$ - 输入均为整数 ### 样例解释 1 输出示例对应如下行为： - 依次发现类型为 $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$ 且不会失败的行为方案有多种，输出任意一种均可。 ### 样例解释 2 高桥君必然会在第一次遇到怪物时失败。 由 ChatGPT 4.1 翻译