[XJTUPC 2024] 雪中楼

Luogu
IDLGP10522
Time1000ms
Memory256MB
DifficultyP3
搜索图论2024O2优化深度优先搜索 DFS拓扑排序链表高校校赛
西安交通大学下雪了,所有楼顶都被积雪覆盖。 在梧桐道上有 $n$ 座房子,自南向北第 $i$ 座房子的标号是 $i$,所有房子的高度互不相同。LNC 从南向北,依次登上每栋楼楼顶,然后他会回头观察他已经到达过的房子,并记录下这些房子中,比当前他所在房子矮的所有房子中,最高的房子的编号,记为 $a_i$。特殊的,当没有房子比当前房子矮的时候,$a_i=0$。 现在给你所有的 $a_i$,要求你还原出所有楼的大小关系。由于高度的具体值未知,你只需要按照高度从低到高,输出房子编号。 可以证明对于任何合法的输入,均存在唯一解。 ## Input 输入第一行一个正整数 $n$ ($1\le n \le 2\times 10^5$),代表房子个数。 接下来一行 $n$ 个非负整数 $a_i$,满足 $0\le a_i <i$,两两之间用空格隔开。 ## Output 输出一行 $n$ 个正整数构成的排列,用空格隔开,表示最终的答案。 [samples] ## Note 假设高度是一个 $1\sim n$ 的排列,那么可以发现高度为 $5, 3, 2, 1, 4$ 是唯一的解,按照高度排名输出得到 $4, 3, 2, 5, 1$。
Samples
Input #1
5
0 0 0 0 2
Output #1
4 3 2 5 1 
API Response (JSON)
{
  "problem": {
    "name": "[XJTUPC 2024] 雪中楼",
    "description": {
      "content": "西安交通大学下雪了,所有楼顶都被积雪覆盖。 在梧桐道上有 $n$ 座房子,自南向北第 $i$ 座房子的标号是 $i$,所有房子的高度互不相同。LNC 从南向北,依次登上每栋楼楼顶,然后他会回头观察他已经到达过的房子,并记录下这些房子中,比当前他所在房子矮的所有房子中,最高的房子的编号,记为 $a_i$。特殊的,当没有房子比当前房子矮的时候,$a_i=0$。 现在给你所有的 $a_i$,要求你还",
      "description_type": "Markdown"
    },
    "platform": "Luogu",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 262144
    },
    "difficulty": {
      "LuoguStyle": "P3"
    },
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "LGP10522"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "西安交通大学下雪了,所有楼顶都被积雪覆盖。\n\n在梧桐道上有 $n$ 座房子,自南向北第 $i$ 座房子的标号是 $i$,所有房子的高度互不相同。LNC 从南向北,依次登上每栋楼楼顶,然后他会回头观察他已经到达过的房子,并记录下这些房子中,比当前他所在房子矮的所有房子中,最高的房子的编号,记为 $a_i$。特殊的,当没有房子比当前房子矮的时候,$a_i=0$。\n\n现在给你所有的 $a_i$,要求你还...",
      "is_translate": false,
      "language": "English"
    }
  ]
}
Full JSON Raw Segments