103334: [Atcoder]ABC333 E - Takahashi Quest

Problem Statement

Takahashi will embark on an adventure.

During the adventure, $N$ events will occur. The $i$-th event $(1\leq i\leq N)$ is represented by a pair of integers $(t _ i,x _ i)$ $(1\leq t _ i\leq 2,1\leq x _ i\leq N)$ and is as follows:

• If $t _ i=1$, he finds one potion of type $x _ i$. He can choose to pick it up or discard it.
• If $t _ i=2$, he encounters one monster of type $x _ i$. If he has a potion of type $x _ i$, he can use one to defeat the monster. If he does not defeat it, he will be defeated.

Determine whether he can defeat all the monsters without being defeated.

If he cannot defeat all the monsters, print -1.

Otherwise, let $K$ be the maximum number of potions he has at some point during the adventure. Let $K _ {\min}$ be the minimum value of $K$ across all strategies where he will not be defeated. Print the value of $K _ {\min}$ and the actions of Takahashi that achieve $K _ {\min}$.

Constraints

• $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)$
• All input values are integers.

Input

The input is given from Standard Input in the following format:

$N$
$t _ 1$ $x _ 1$
$t _ 2$ $x _ 2$
$\vdots$
$t _ N$ $x _ N$

Output

If Takahashi cannot defeat all the monsters, print -1. If he can, print the value of $K _ {\min}$ in the first line, and in the second line, for each $i$ such that $t _ i=1$ in ascending order, print 1 if he picks up the potion found at the $i$-th event, and 0 otherwise, separated by spaces. If multiple sequences of actions achieve $K _ {\min}$ and allow him to finish the adventure without being defeated, you may print any of them.

Sample Input 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

Sample Output 1

3
1 1 1 0 0 1 0 1

The sample output corresponds to the following actions:

• Find potions of types $2,3,1$ in this order. Pick up all of them.
• Find potions of types $3,2$ in this order. Do not pick up any of them.
• Encounter a type-$3$ monster. Use one type-$3$ potion to defeat it.
• Find a type-$3$ potion. Pick it up.
• Find a type-$3$ potion. Do not pick it up.
• Encounter a type-$3$ monster. Use one type-$3$ potion to defeat it.
• Find a type-$3$ potion. Pick it up.
• Encounter a type-$2$ monster. Use one type-$2$ potion to defeat it.
• Encounter a type-$3$ monster. Use one type-$3$ potion to defeat it.
• Encounter a type-$1$ monster. Use one type-$1$ potion to defeat it.

In this sequence of actions, the value of $K$ is $3$.

There is no way to avoid defeat with $K\leq 2$, so the sought value of $K _ {\min}$ is $3$. There are multiple sequences of actions that satisfy $K=3$ and allow him to avoid defeat; you may print any of them.

Sample Input 2

4
2 3
1 4
2 1
1 2

Sample Output 2

-1

He will inevitably be defeated by the first monster he encounters.

Sample Input 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

Sample Output 3

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

问题描述

高桥君将开始一次冒险。

在冒险过程中，会发生$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}$得以实现的高桥君的行动。

约束

• $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}$的值，在第二行中，对于$t _ i=1$的每个$i$从小到大顺序，如果他在第$i$个事件中拾起发现的药水，打印1，否则打印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$的值为$3$。

没有使$K\leq 2$的情况下避免失败的方法，因此所寻求的$K _ {\min}$的值为$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