問題一覧 > 通常問題

No.3086 Re One Two

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 84
作問者 : yuusaan / テスター : kazuppa 👑 amentorimaru
2 ProblemId : 11404 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2025-04-04 10:22:24

ストーリー

???「Reはもちろん「レ点」って意味だよ」

ゆ~さんは漢文ドリルを進めています。まだ始めたばかりのため、今日の内容は漢文の読む順番についてです。

しかし、そのドリルに書かれている漢文はおおよそ人間用とは思えないほど長かったため、ゆ~さんは漢文の返り点を入力すると読む順番が出力されるプログラムが欲しくなりました。

そして、あなたにその仕事を依頼しました。恐らく、機械にやらせるにしてもなかなか面倒な部類の仕事ですが...

問題文

NN 個の文字があり、それぞれ 文字 1,,N1,\dots,N と番号が割り振られています。

文字 ii には Ai,BiA_i,B_i の数字が割り振られており、 NN 個の文字が下記のルールに従った順番でちょうど一回ずつ読まれます。

  • Ai=1A_i=1 である時、文字 i+1i+1 の次に読む
  • Bi=2B_i=2 である時、j>ij>i かつ Bj=1B_j=1 である最小の jj である 文字 jj の次に読む
  • 上記に該当しない場合、小さい番号の文字を先に読む

制約より、文字の読む順番は一意に定まり、それはすべての文字をちょうど一度ずつ読むものであることが保証されます。

k=1,,Nk=1,\dots,N において、 kk 番目に読まれる 文字の番号を NN 行で答えてください。

制約が複雑である点に注意してください。

入力

NN
A1 B1A_1\ B_1
A2 B2A_2\ B_2
\vdots
AN BNA_N\ B_N

制約

  • 2N2×1052\le N\le 2\times10^5
  • AiA_i\in { 0,10,1 }
  • BiB_i\in { 0,1,20,1,2 }
  • AN=0A_N=0
  • BN2B_N\neq 2
  • 11 以上 NN 以下のすべての ii について、B1,B2,,BiB_1,B_2,\dots,B_i のうち 11 と同値であるものの個数を DD22 と同値であるものの個数を EE をすると
    • DED\le E
    • ED1E-D \le 1
  • B1,B2,,BNB_1,B_2,\dots,B_N のうち 11 と同値であるものの個数と 22 と同値であるものの個数は等しい
  • Ai=1A_i=1 ならば Bi+11B_{i+1}\neq 1
  • Ai=1A_i=1 ならば Bi2B_i\neq 2
  • Bi=2B_i = 2 ならば Bi+1=0B_{i+1} = 0
  • 入力はすべて整数

出力

NN 行出力してください。ii 行目には ii 番目に読む文字の番号を出力してください。

最後に改行してください。

サンプル

サンプル1
入力
3
0 0
1 0
0 0
出力
1
3
2

まず、文字 11 が読まれます。次に、A2=1A_2=1 であるため、次の文字 33 が先に読まれ、文字 22 はその後に読まれます。

サンプル2
入力
5
0 0
1 0
0 2
0 0
0 1
出力
1
4
5
3
2

以下の順で文字が読まれます。

  • 文字 11 が読まれる。
  • A2=1,B3=2A_2=1,B_3=2 であるため、先に文字 44 が読まれる。
  • その次である文字 55 が読まれる。
  • 文字 55 が読まれたため、文字 33 が読めるようになる。文字 33 が読まれる。
  • 文字 33 が読まれたため、文字 22 が読めるようになる。文字 22 が読まれる。

サンプル3
入力
10
0 2
1 0
1 0
0 0
1 1
0 2
0 0
1 0
0 0
0 1
出力
4
3
2
7
9
8
10
6
5
1

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。