No.3086 Re One Two
タグ : / 解いたユーザー数 85
作問者 :
kazuppa
👑
amentorimaru
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もしくは右上の雲マークをクリックしてアカウントを作成してください。