問題一覧 > 通常問題

No.3086 Re One Two

レベル : / AI推定難易度 : 1200 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : (AC するまで非表示) / 解いたユーザー数 85
作問者 : yuusaan / テスター : kazuppa 👑 amentorimaru
お気に入りにしたユーザー ProblemId : 11404 / 自分の提出
問題文最終更新日: 2025-04-04 10:22:24
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
yukicoder contest 463 (順位表) の他の問題:

Story

???: "Re means "reten", of course."

Yu~-san is working through a kanbun drill. Having only just started, today's topic is the order in which kanbun is read.

However, the kanbun written in the drill was so long that it hardly seemed meant for humans, so Yu~-san came to want a program that outputs the reading order when given the kaeriten of the kanbun as input.

And so, Yu~-san has asked you to do this job. It is probably a rather troublesome kind of job, even for a machine...

Problem Statement

There are $N$ characters, numbered character $1,\dots,N$.

Character $i$ is assigned the numbers $A_i,B_i$, and the $N$ characters are each read exactly once, in the order determined by the following rules.

  • If $A_i=1$, it is read right after character $i+1$.
  • If $B_i=2$, it is read right after character $j$, where $j$ is the smallest index such that $j>i$ and $B_j=1$.
  • In cases not covered by the above, the character with the smaller number is read first.

By the constraints, it is guaranteed that the reading order of the characters is uniquely determined and that it reads every character exactly once.

For $k=1,\dots,N$, output the number of the character read $k$-th, over $N$ lines.

Note that the constraints are complex.

Input

$N$
$A_1\ B_1$
$A_2\ B_2$
$\vdots$
$A_N\ B_N$

Constraints

  • $2\le N\le 2\times10^5$
  • $A_i\in $ { $0,1$ }
  • $B_i\in $ { $0,1,2$ }
  • $A_N=0$
  • $B_N\neq 2$
  • For every $i$ from $1$ to $N$, letting $D$ be the number of values equal to $1$ among $B_1,B_2,\dots,B_i$ and $E$ be the number of values equal to $2$ among them,
    • $D\le E$
    • $E-D \le 1$
  • The number of values equal to $1$ and the number of values equal to $2$ among $B_1,B_2,\dots,B_N$ are equal.
  • If $A_i=1$, then $B_{i+1}\neq 1$.
  • If $A_i=1$, then $B_i\neq 2$.
  • If $B_i = 2$, then $B_{i+1} = 0$.
  • All inputs are integers.

Output

Output $N$ lines. On the $i$-th line, output the number of the character read $i$-th.

Print a newline at the end.

Sample

Sample 1
Input
3
0 0
1 0
0 0
Output
1
3
2

First, character $1$ is read. Next, since $A_2=1$, the following character $3$ is read first, and character $2$ is read after it.

Sample 2
Input
5
0 0
1 0
0 2
0 0
0 1
Output
1
4
5
3
2

The characters are read in the following order.

  • Character $1$ is read.
  • Since $A_2=1,B_3=2$, character $4$ is read first.
  • The next character, character $5$, is read.
  • Since character $5$ has been read, character $3$ can now be read. Character $3$ is read.
  • Since character $3$ has been read, character $2$ can now be read. Character $2$ is read.

Sample 3
Input
10
0 2
1 0
1 0
0 0
1 1
0 2
0 0
1 0
0 0
0 1
Output
4
3
2
7
9
8
10
6
5
1

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