European Girls' Olympiad in Informatics: 2023 Day 2 Problem 1
Every four years, the students of Lund come together to organize the Lund Carnival. For a few days, a park fills with tents where all kinds of festive activities take place. The person in charge of making this happen is the carnival general.
In total, there have been carnivals, each with a different general. The generals are numbered from to in chronological order. Every general has given their opinion on how good their predecessors were, by publishing a ranking of the generals in order from best to worst.
The next Lund Carnival will be in 2026. In the meantime, all past carnival generals have gathered to take a group photo. However, it would be awkward if generals and (where end up next to each other if is strictly in the second half of 's ranking.
For example:
- If general has given the ranking
3 2 1 0
, then can stand next to , or , but not or . - If general has given the ranking
4 3 2 1 0
, then can stand next to , or , but not or .
Note that it is fine if one general is exactly in the middle of another's ranking.
The following figure illustrates sample 1. Here, general stands next to generals and , and general stands next to general only.
You are given the rankings that the generals published. Your task is to arrange the generals in a row, so that if and are adjacent (where ) then is not strictly in the second half of 's ranking.
Input Specification
The first line contains the positive integer , the number of generals.
The following lines contain the rankings. The first of these lines contains general 's ranking, the second line contains general 's ranking, and so on until general . General is absent since general didn't have any predecessors to rank.
The ranking of general is a list with integers in which every integer from to occurs exactly once. Specifically, is the best and is the worst general according to general .
Output Specification
Print a list of integers, an ordering of the numbers , such that for each pair of adjacent numbers, neither is strictly in the second half of the other's ranking.
It can be proven that a solution always exists. If there are multiple solutions, you may print any of them.
Constraints and Scoring
- .
- for .
Your solution will be tested on a set of test groups, each worth a number of points. Each test group contains a set of test cases. To get the points for a test group you need to solve all test cases in the test group.
Group | Score | Limits |
---|---|---|
1 | 11 | The ranking of general will be for all such that . |
2 | 23 | The ranking of general will be for all such that . |
3 | 29 | |
4 | 37 | No additional constraints. |
Sample Input 1
6
0
1 0
2 1 0
3 2 1 0
4 3 2 1 0
Sample Output 1
4 2 5 3 1 0
Sample Input 2
5
0
0 1
0 1 2
0 1 2 3
Sample Output 2
2 0 4 1 3
Sample Input 3
4
0
1 0
0 2 1
Sample Output 3
3 0 1 2
Comments