CF141C Queue

在 Main Berland 银行，有 $n$ 个人站在收银台前排队，每个人都知道自己和队列中其他所有人的身高 $h_{i}$。每个人心中记着一个数字 $a_{i}$ —— 站在他/她前面并且比他/她高的人数。 过了一会儿，收银员去吃午饭了，队伍中的人进到候客厅随意入座。当午餐时间结束时，大家都不记得排队的具体顺序了，但每个人都还记得属于自己的 $a_{i}$。 你的任务是，如果可能的话，恢复这些人原本的排队顺序。可能存在多个符合条件的顺序，你需要输出其中任意一个。同时，你还需要给出一组可能的身高 $h_{i}$，使得对于每个人 $a_{i}$ 都计数正确。

第一行输入一个整数 $n$，表示排队的人数（$1 \leq n \leq 3000$）。接下来 $n$ 行，每行包含 “$name_{i}$ $a_{i}$”，其中 $name_{i}$ 是仅由小写拉丁字母组成的非空字符串，长度不超过 $10$（第 $i$ 个人的名字），$a_{i}$ 是整数（$0 \leq a_{i} \leq n-1$），表示在他前面并且身高比他高的人数。保证所有的 $name_{i}$ 均不相同。

如果不存在任何一种合法的排队顺序，则输出一行 “-1”。否则，输出 $n$ 行，每行 “$name_{i}$ $h_{i}$”，$h_{i}$ 是一个介于 $1$ 到 $10^{9}$ 之间的整数，表示名字为 $name_{i}$ 的这个人可能的身高。要求输出的人按排队顺序（从队首到队尾）排列。$h_{i}$ 不要求唯一。

由 ChatGPT 5 翻译