Sort Arrays

AtCoder

IDabc437_e

Time2000ms

Memory256MB

Difficulty—

There are $N+1$ sequences $A_0, A_1, \ldots, A_{N}$. $A_i$ is defined as follows: * $A_0$ is an empty sequence. * $A_i\ (1\leq i\leq N)$ is a sequence obtained by appending an integer $y_i$ to the end of the sequence $A_{x_i}\ (0\leq x_i\lt i)$. Find the permutation $P=(P_1, P_2,\ldots,P_N)$ of $(1,2,\ldots,N)$ that satisfies the following condition: * For $i = 1,2,\ldots,N-1$, one of the following holds: * $A_{P_i}$ is lexicographically smaller than $A_{P_{i+1}}$. * $A_{P_i}= A_{P_{i+1}}$ and $P_i\lt P_{i+1}$ In other words, when $A_1,A_2,\ldots,A_N$ are arranged in lexicographical order (when there are multiple equal sequences, arrange those with smaller indices first), $P$ is the sequence of indices that appears in that arrangement. What is the lexicographical order of sequences?A sequence $S = (S_1,S_2,\ldots,S_{|S|})$ is **lexicographically smaller** than a sequence $T = (T_1,T_2,\ldots,T_{|T|})$ if one of the following two conditions holds. Here, $|S|$ and $|T|$ represent the lengths of $S$ and $T$, respectively. 1. $|S| \lt |T|$ and $(S_1,S_2,\ldots,S_{|S|}) = (T_1,T_2,\ldots,T_{|S|})$. 2. There exists an integer $1 \leq i \leq \min\lbrace |S|, |T| \rbrace$ such that both of the following hold: * $(S_1,S_2,\ldots,S_{i-1}) = (T_1,T_2,\ldots,T_{i-1})$ * $S_i$ is (numerically) smaller than $T_i$. ## Constraints * $1\leq N\leq 3\times 10^5$ * $0\leq x_i\lt i$ * $1\leq y_i\leq 10^9$ * All input values are integers. ## Input The input is given from Standard Input in the following format: $N$ $x_1$ $y_1$ $x_2$ $y_2$ $\vdots$ $x_N$ $y_N$ [samples]

Samples

Input #1

Output #1

2 4 3 1

$A_1 = (2), A_2 = (1), A_3 = (1, 2), A_4 = (1)$, so $P=(2,4,3,1)$.

Input #2

Output #2

1 2 3 4 5

$A_1 = A_2 = A_3 = A_4 = A_5 = (1)$.

Input #3

10
0 305186313
1 915059758
0 105282054
1 696409999
3 185928366
3 573289179
6 254538849
3 105282054
5 696409999
8 168629803

Output #3

3 8 10 5 9 6 7 1 4 2

API Response (JSON)

{
  "problem": {
    "name": "Sort Arrays",
    "description": {
      "content": "There are $N+1$ sequences $A_0, A_1, \\ldots, A_{N}$. $A_i$ is defined as follows: *   $A_0$ is an empty sequence. *   $A_i\\ (1\\leq i\\leq N)$ is a sequence obtained by appending an integer $y_i$ to th",
      "description_type": "Markdown"
    },
    "platform": "AtCoder",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "abc437_e"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "There are $N+1$ sequences $A_0, A_1, \\ldots, A_{N}$. $A_i$ is defined as follows:\n\n*   $A_0$ is an empty sequence.\n*   $A_i\\ (1\\leq i\\leq N)$ is a sequence obtained by appending an integer $y_i$ to th...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments