P16539 [EGOI 2026] Ferris Wheel / Ferris Wheel

In the main square of Cesenatico, there is a colorful Ferris wheel, one of the city’s landmark attractions. During winter, the Ferris wheel was dismantled and stored away. But now summer is coming, and it is time to assemble it again. The dismantled parts have just arrived at the square, and with your help, we are ready to put them all together. In front of you there are $N$ separate cabins, and they need to be connected to each other in a circular way to form a Ferris wheel. These cabins are numbered from $0$ to $N-1$, but they are not necessarily arranged in the order in which they should be connected. Each cabin has a special connection point used to connect clockwise to the next cabin. Each connection point can be of one of two types: - Type [`+`]: it can only connect to a cabin with a larger number. - Type [`-`]: it can only connect to a cabin with a smaller number. In the sample below, cabin $2$ has a [`+`] type connection point. This means that the next cabin clockwise must be cabin $3$ or $4$. :::align{center}  $N=5$, five separate cabins, each with a [`+`] or [`-`] type connection point. ::: Given the number of cabins and the type of connection point on each cabin, your task is to determine whether these $N$ cabins can be assembled into a Ferris wheel. If the answer is yes, you also need to find one possible clockwise order of the cabins on the Ferris wheel. :::align{center}  A valid Ferris wheel that can be assembled from the five cabins above. ::: Figure 2 shows a valid Ferris wheel assembled from the five cabins in Figure 1. Formally, a valid cabin order is a sequence of numbers $C_0, C_1, \dots, C_{N-1}$ with the following properties: - Each number from $0$ to $N-1$ appears in the sequence exactly once. - For each $0

The input consists of two lines. The first line contains an integer $N$, representing the number of cabins. The second line contains a string $S$ of length $N$, consisting of the characters '`+`' and '`-`'. If $S_i = $ '`+`', then cabin $i$ has a [`+`] type connection point. If $S_i = $ '`-`', then cabin $i$ has a [`-`] type connection point.

If there is no order that satisfies the conditions, output `NO`. Otherwise, output `YES`, and on the next line output $N$ integers, the cabin numbers on a valid Ferris wheel in clockwise order. You may start from any cabin. If there are multiple solutions, you may output any one of them.

### Sample Explanation **First example.** There are three cabins. Since all connection points are of type [`+`], each cabin must be followed by a cabin with a larger number. It can be proven that there is no arrangement of these three cabins that satisfies this condition, so the answer is `NO`. **Second example.** See Figure 1 and Figure 2 in the statement. There are five cabins. We must arrange them clockwise so that: - cabins 0 and 2 (connection point type [`+`]) are followed by a cabin with a larger number; - cabins 1, 3, and 4 (connection point type [`-`]) are followed by a cabin with a smaller number. The figure below shows a Ferris wheel that satisfies all these conditions. For all [`+`] type connection points, the condition holds because $0 < 3$ and $2 < 4$. For all [`-`] type connection points, the condition holds because $1 > 0$, $3 > 2$, and $4 > 1$. There is more than one valid output for this Ferris wheel: besides `0 3 2 4 1`, you can also output `3 2 4 1 0`, `2 4 1 0 3`, `4 1 0 3 2`, or `1 0 3 2 4`. :::align{center}  The Ferris wheel for the second example (this figure is the same as Figure 2). ::: In the third example, there are seven cabins: all connection points are of type [`-`], except the last one which is of type [`+`]. Therefore, we must arrange the cabins so that each cabin is followed by a smaller-numbered cabin, except cabin 6, which must be followed by a larger-numbered cabin. It can be proven that no such order exists, so the answer is `NO`. The figures below show the Ferris wheels corresponding to the outputs of the last two samples. :::align{center}  The Ferris wheel for the fourth sample. ::: :::align{center}  The Ferris wheel for the fifth sample. ::: ### Constraints - $3 \leq N \leq 300000$。 - $S_i = $ '`+`' or '`-`'。 ### Scoring Your program will be tested on testdata divided into several subtasks. To get the score for a subtask, you must solve all testdata in that subtask correctly. - **Subtask 0** [$0$ points]: samples. - **Subtask 1** [$16$ points]: $N = 3$. - **Subtask 2** [$13$ points]: the string $S$ contains exactly one '+'. - **Subtask 3** [$24$ points]: the characters '+' and '-' in $S$ alternate; that is, for every $0 \le i \le N - 2$, we have $S_i \neq S_{i+1}$. - **Subtask 4** [$23$ points]: $N \le 1000$. - **Subtask 5** [$24$ points]: no additional constraints. Translated by ChatGPT 5