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

输入 #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

输入 #2

4
2 3
1 4
2 1
1 2

输出 #2

-1

输入输出样例 #3

输入 #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

说明/提示

限制条件

• $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 翻译