P16539 [EGOI 2026] 摩天轮 / Ferris Wheel
题目描述
切塞纳蒂科（Cesenatico）的主广场上有一座色彩缤纷的摩天轮，这是该市的标志性景点之一。在冬天时，摩天轮已被拆卸并储存了起来。但现在夏天快到了，是时候重新组装它了！那些被拆的零件刚抵达广场，在你的帮助下，我们准备把它们全部组装起来。
在你面前有 $N$ 个独立的座舱，需要以环形方式相互连接，组成一个摩天轮。这些座舱编号从 $0$ 到 $N-1$，但并不一定按照它们应该被连接的顺序排列。
每个座舱都带有一个特殊的连接点，用于按顺时针方向连接到下一个座舱。每个连接点有两种可能的类型：
- 类型 [`+`]：只能连接到编号更大的座舱；
- 类型 [`-`]：只能连接到编号更小的座舱。
在下面的样例中，座舱 $2$ 有一个 [`+`] 类型的连接点。这意味着按顺时针方向连接的下一个座舱必须是座舱 $3$ 或 $4$。
:::align{center}
$N=5$，五个独立的座舱，每个都有一个 [`+`] 或 [`-`] 类型的连接点。
:::
给定座舱的数量和它们的连接点类型，你的任务是判断是否可以将这 $N$ 个座舱组装成一个摩天轮。如果答案是可以，你还需要找出一种座舱在摩天轮上的排列顺序。
:::align{center}
可以用上述五个座舱组装出的合法摩天轮。
:::
图 2 显示了用图 1 中的五个座舱组装出的一个合法摩天轮。
形式化来说，合法的座舱顺序是一个数字序列 $C_0, C_1, \dots, C_{N-1}$，且具有以下性质：
- 从 $0$ 到 $N-1$ 的每个数字在序列中恰好出现一次。
- 对于每个 $0
输入格式
输入由两行组成。第一行包含一个整数 $N$，表示座舱的数量。
第二行包含一个长度为 $N$ 的字符串 $S$，由字符 '`+`' 和 '`-`' 组成。如果 $S_i = $ '`+`'，则座舱 $i$ 的连接点类型为 [`+`]。如果 $S_i = $ '`-`'，则座舱 $i$ 的连接点类型为 [`-`]。
输出格式
如果没有满足条件的顺序，输出 `NO`。
否则，输出 `YES`，并在下一行输出 $N$ 个整数，即合法摩天轮上座舱的编号，按顺时针顺序排列，可以从任意编号开始。如果有多种解法，你可以输出其中任意一种。
说明/提示
### 样例解释
**第一个例子。** 给定三个座舱。由于所有连接点都是 [`+`] 类型，每个座舱都必须后面紧跟着一个编号更大的座舱。可以证明，这三个座舱没有一种排列方式满足此条件，因此答案是 `NO`。
**第二个例子。** 参见问题描述中的图 1 和图 2。给定五个座舱。我们必须按顺时针方向排列它们，使得：
- 座舱 0 和 2（连接点类型为 [`+`]）后面紧跟着一个编号更大的座舱；
- 座舱 1、3 和 4（连接点类型为 [`-`]）后面紧跟着一个编号更小的座舱。
下图显示了一个满足所有这些条件的摩天轮。对于所有 [`+`] 类型的连接点，条件成立，因为 $0 < 3$ 且 $2 < 4$。对于所有 [`-`] 类型的连接点，条件成立，因为 $1 > 0$，$3 > 2$ 且 $4 > 1$。对应这个摩天轮的输出不止一种：除了 `0 3 2 4 1`，你也可以输出 `3 2 4 1 0`，`2 4 1 0 3`，`4 1 0 3 2`，或 `1 0 3 2 4`。
:::align{center}
第二个例子的摩天轮（此图与图 2 相同）。
:::
在第三个例子中，我们有七个座舱：所有连接点都是 [`-`] 类型，除了最后一个是 [`+`] 类型。因此，我们必须安排座舱，使得每个座舱后面都跟着一个编号更小的座舱，除了座舱 6，它必须跟着一个编号更大的座舱。可以证明，不存在这样的顺序，所以答案是 `NO`。
下图显示了对应于最后两个样例输出的摩天轮。
:::align{center}
第四个样例的摩天轮。
:::
:::align{center}
第五个样例的摩天轮。
:::
### 约束条件
- $3 \leq N \leq 300000$。
- $S_i = $ '`+`' or '`-`'。
### 评分方式
你的程序将在分成若干子任务的测试数据上进行测试。要获得某个子任务的分数，你必须正确解出该子任务中所有的测试数据。
- **子任务 0** [$0$ 分]：样例。
- **子任务 1** [$16$ 分]：$N = 3$。
- **子任务 2** [$13$ 分]：字符串 $S$ 中恰好有一个 '+'。
- **子任务 3** [$24$ 分]：字符串 $S$ 中的字符 '+' 和 '-' 交替出现；也就是说，对于每个 $0 \le i \le N - 2$，满足 $S_i \neq S_{i+1}$。
- **子任务 4** [$23$ 分]：$N \le 1000$。
- **子任务 5** [$24$ 分]：没有额外的约束条件。