Lining Up 2

题目描述

有 $N$ 个人排成一列：第 $1$ 个人、第 $2$ 个人、$\ldots$、第 $N$ 个人。 给出这些人的排列作为长度为 $N$ 的序列 $A=(A _ 1,A _ 2,\ldots,A _ N)$。 $A _ i\ (1\leq i\leq N)$ 表示如下信息：

如果 $A _ i=-1$，第 $i$ 个人在队伍的最前面； 如果 $A _ i\neq -1$，第 $i$ 个人紧跟在第 $A _ i$ 个人的后面。

按从前到后的顺序打印人编号。

输入格式

输入从标准输入按如下格式给出： $N$ $A _ 1$ $A _ 2$ $\ldots$ $A _ N$

输出格式

如果第 $s _ 1$ 个人、第 $s _ 2$ 个人、$\ldots$、第 $s _ N$ 个人按此顺序站成一列，则按此顺序用空格分隔打印 $s _ 1$、$s _ 2$、$\ldots$、$s _ N$。

6
4 1 -1 5 3 2

3 5 4 1 2 6

10
-1 1 2 3 4 5 6 7 8 9

1 2 3 4 5 6 7 8 9 10

30
3 25 20 6 18 12 26 1 29 -1 21 17 23 9 8 30 10 15 22 27 4 13 5 11 16 24 28 2 19 7

10 17 12 6 4 21 11 24 26 7 30 16 25 2 28 27 20 3 1 8 15 18 5 23 13 22 19 29 9 14

提示

$1\leq N\leq3\times10 ^ 5$ $A _ i=-1$ or $1\leq A _ i\leq N\ (1\leq i\leq N)$ 给定的信息下恰好存在一种将 $N$ 个人排列一致的方式。 所有输入值均为整数。如果第 $3$ 个人、第 $5$ 个人、第 $4$ 个人、第 $1$ 个人、第 $2$ 个人和第 $6$ 个人从前到后按此顺序站成队伍，则该排列与给定的信息相符。 确实，可以看出：

第 $1$ 个人紧跟在第 $4$ 个人后面， 第 $2$ 个人紧跟在第 $1$ 个人后面， 第 $3$ 个人在队伍最前面， 第 $4$ 个人紧跟在第 $5$ 个人后面， 第 $5$ 个人紧跟在第 $3$ 个人后面，且 第 $6$ 个人紧跟在第 $2$ 个人后面。

因此，按此顺序用空格分隔打印 $3$、$5$、$4$、$1$、$2$ 和 $6$。

标签: AtCoder|abc337C

来源

AtCoder|abc337C