P9467 [EGOI 2023] Carnival General / Carnival General

Day 2 Problem A. Translated from [EGOI2023 carnival](https://egoi23.se/assets/tasks/day2/carnival.pdf)。 [](https://creativecommons.org/licenses/by-sa/3.0/)

Every four years, students in Lund gather and host the Lund Carnival. Over a few days, the park fills up with tents and many kinds of celebrations are held. The person responsible for organizing all of this is called the Carnival General. There are $N$ carnivals, each with a different general. These generals are numbered from $0$ to $N-1$ in chronological order. Each general $i$ gives their opinion on previous generals: they publish a ranking of generals $0,1,\cdots,i-1$ from best to worst. The next Lund Carnival will be held in 2026. During that time, all former carnival generals got together to take a group photo. However, it will be awkward if generals $i$ and $j$ (where $i < j$) end up standing next to each other, and $i$ is ranked **strictly** in the bottom half of the ranking given by $j$. For example: - If the ranking given by general $4$ is `3 2 1 0`, then $4$ may stand next to $3$ or $2$, but may not stand next to $1$ or $0$. - If the ranking given by general $5$ is `4 3 2 1 0`, then $5$ may stand next to $4,3,2$, but may not stand next to $1$ or $0$. The figure below shows Sample $1$. In it, general $5$ stands next to generals $2$ and $3$, and general $4$ stands only next to general $2$.  You know all the rankings given by the generals. Your task is to arrange all generals $0,1,\cdots,N-1$ in a line such that whenever $i$ and $j$ stand next to each other (where $i < j$), then $i$ is **not** ranked strictly in the bottom half of the ranking given by $j$.

The first line contains an integer $N$, the total number of generals. The next $N-1$ lines contain all rankings. The first of these lines is the ranking given by general $1$, the second is the ranking given by general $2$, and so on up to general $N-1$. General $0$ is not included in the input, because general $0$ has no previous generals to rank. The ranking of general $i$ is a list of length $i$: $p_{i,0},p_{i,1},\cdots,p_{i,i-1}$, where each integer from $0$ to $i-1$ appears exactly once. Specifically, in the ranking of general $i$, $p_{i,0}$ is the best general and $p_{i,i-1}$ is the worst general.

Output a sequence of integers: a permutation of $0,1,\cdots,N-1$, such that for every pair of adjacent integers, neither one is in the bottom half of the other one's ranking. It can be proven that a solution always exists. If there are multiple solutions, you may output any of them.

**Sample $1$ Explanation** Sample $1$ satisfies the requirements of Subtask 1. In the sample, generals $2$ and $3$ cannot stand next to general $0$, and generals $4$ and $5$ cannot stand next to generals $0$ and $1$. The sample output is shown in the figure above. --- **Sample $2$ Explanation** Sample $2$ satisfies the requirements of Subtask 2. In the sample, general $2$ cannot stand next to general $1$, general $3$ cannot stand next to general $2$, and general $4$ cannot stand next to generals $3$ and $2$. --- **Sample $3$ Explanation** Sample $3$ satisfies the requirements of Subtask 3. In the sample, only the two pairs $(1,3)$ and $(0,2)$ of generals cannot stand next to each other. Therefore, if the arrangement is `3 0 1 2`, there will be no conflict. Another possible answer is `0 1 2 3`. --- **Constraints** For all testdata, $2\le N\le 10^3$, $0\le p_{i,0},p_{i,1},\cdots,p_{i,i-1}\le i-1$。 - Subtask 1 ($11$ points): the ranking given by general $i$ is $i-1,i-2,\cdots,0$. - Subtask 2 ($23$ points): the ranking given by general $i$ is $0,1,\cdots,i-1$. - Subtask 3 ($29$ points): $N\le 8$. - Subtask 4 ($37$ points): no additional constraints. Translated by ChatGPT 5