P7726 Astral Detector (Astral Detector)

By exploring the ancient archives, you successfully built the Astral Detector. You need to use it to discover hidden astral technology.

To find the astral technology, you first need to obtain a string of astral codes—it is a **permutation** of $1 \sim n$. The Astral Detector can, for a given length $l$, return the **minimum value of an interval of length $l$** in the code. Unfortunately, the minimum values of all intervals of length $l$ are mixed together. What you get is only $n$ **multisets** $S_1, \ldots , S_n$: - $S_i$ denotes the multiset formed by the minimum values of all intervals of length $i$. You need to reconstruct one possible astral code from these $S_i$. It is guaranteed that at least one correct astral code exists.

The first line contains an integer $n$, representing the length of the astral code. The next $n$ lines follow. The $i$-th line contains $n - i + 1$ integers (there are $n - i + 1$ intervals of length $i$), representing each element in the multiset $S_i$. Note that the order of the elements is **arbitrary**, and is not necessarily the left-to-right order of the intervals.

Output one line with $n$ integers $p_1, p_2, \ldots , p_n$, representing the astral code you reconstructed. If there are multiple feasible solutions, you may output any one of them.

**[Sample 1 Explanation]** The astral code in the sample output is: $p = [3, 1, 2, 4]$. The multiset of minimum values of intervals of length $1$: $S_1 = \{ 3, 1, 2, 4 \} = \{ 4, 3, 2, 1 \}$. The multiset of minimum values of intervals of length $2$: $S_2 = \{ \min(3, 1), \min(1, 2), \min(2, 4) \} = \{ 1, 1, 2 \} = \{ 1, 2, 1 \}$. The multiset of minimum values of intervals of length $3$: $S_3 = \{ \min(3, 1, 2), \min(1, 2, 4) \} = \{ 1, 1 \}$. The multiset of minimum values of intervals of length $4$: $S_4 = \{ \min(3, 1, 2, 4) \} = \{ 1 \}$. Each $S_i$ corresponds to the input. Other feasible answers are also accepted, such as $p = [4, 2, 1, 3]$. --- **[Constraints]** **This problem uses bundled testdata.** For $100\%$ of the data: $2 \le n \le 800$. | Subtask ID | Score | $n \le$ | Special Constraints | |:-:|:-:|:-:|:-:| | $1$ | $26$ | $6$ | None | | $2$ | $24$ | $16$ | None | | $3$ | $12$ | $800$ | For each $i \in [1, n]$, there are no two equal elements in $S_i$ | | $4$ | $38$ | $800$ | None | Translated by ChatGPT 5