E - Takahashi Quest Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 450 点

問題文

高橋くんは冒険に出ようとしています。

冒険では、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 のポーションを 1 つ発見する。高橋くんは、発見したポーションを拾うか捨てるかのどちらかを選択する。
  • t _ i=2 のとき、タイプ x _ i のモンスター 1 体と遭遇する。高橋くんがタイプ x _ i のポーションを持っている場合、それを 1 つ消費することでモンスターを撃退することができる。モンスターを撃退しなかった場合、高橋くんは敗北する。

高橋くんが敗北することなく全てのモンスターを撃退することができるか判定してください。

高橋くんが全てのモンスターを撃退することができない場合、-1 を出力してください。

高橋くんが全てのモンスターを撃退することができる場合、高橋君が冒険の途中で持っているポーションの個数の最大値を K とします。 高橋くんが敗北しないような戦略全体にわたる K の最小値を K _ {\min} とします。 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 を出力せよ。 高橋くんが全てのモンスターを撃退することができる場合、1 行目には K _ {\min} の値を、2 行目には 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 のポーションを 1 つ消費してモンスターを撃退する。
  • タイプ 3 のポーションを発見する。このポーションを拾う。
  • タイプ 3 のポーションを発見する。このポーションを拾わない。
  • タイプ 3 のモンスターと遭遇する。持っているタイプ 3 のポーションを 1 つ消費してモンスターを撃退する。
  • タイプ 3 のポーションを発見する。このポーションを拾う。
  • タイプ 2 のモンスターと遭遇する。持っているタイプ 2 のポーションを 1 つ消費してモンスターを撃退する。
  • タイプ 3 のモンスターと遭遇する。持っているタイプ 3 のポーションを 1 つ消費してモンスターを撃退する。
  • タイプ 1 のモンスターと遭遇する。持っているタイプ 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

Score : 450 points

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