Score : $450$ points

问题描述

高桥将要开始一场冒险。

在冒险过程中，将会发生 $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}$ 的行动方案。

以上为通义千问 qwen-max 翻译，仅供参考。

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 0 1 0 0 0 0 1 1 0 1 0 1 0 0 0

update @ 2024/3/10 01:20:04