AT_abc333_e [ABC333E] Takahashi Quest

[problemUrl]: https://atcoder.jp/contests/abc333/tasks/abc333_e 高橋くんは冒険に出ようとしています。 冒険では、$ 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} $ を達成する高橋くんの行動を出力してください。

入力は以下の形式で標準入力から与えられる。 > $ 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\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) $ - 入力はすべて整数 ### Sample Explanation 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 $ を満たして高橋くんが敗北しない行動は複数ありますが、どれを出力しても構いません。 ### Sample Explanation 2 高橋くんはかならず最初に遭遇するモンスターに敗北してしまいます。