Problem Description

With the Olympics approaching, students are becoming more and more enthusiastic about sports. As NOI2008 is coming, the school is planning to hold a table tennis tournament. Student Z, a hardcore table tennis fan, sees this as a great chance to show his skills, so he eagerly signs up.

This table tennis tournament uses a single-elimination format: winners advance. There are exactly $n$ students signed up ($n$ is an integer power of $2$, so we may assume $n = 2^k$). Therefore, after the first round, $2^{k-1}$ students will be eliminated and the other $2^{k-1}$ students will advance to the next round; after the second round, $2^{k-2}$ students advance to the next round, and so on, until after $k$ rounds the champion and runner-up are decided. Specifically, everyone has an initial ID from $1\sim n$. Student Z has ID $1$. All students have distinct IDs. They will be assigned to $n$ positions, and then play according to a bracket like the one below:

The figure above shows the bracket when $n=8$.

To attract more students to participate, the prizes are very generous. A player eliminated in round $i$ will receive $a_i$ yuan, and the champion will receive the highest prize $a_{k+1}$ yuan. Clearly, the prizes satisfy $a_1<a_2<\cdots<a_{k+1}$.

In the warm-up matches before the official tournament, Student Z keeps losing. After careful analysis, he realizes the main reason is not his technique, but that the few students who beat him have playing styles that counter his. Once they face each other, he naturally loses. Student Z thinks: if only he could avoid these players in the official tournament!

Assume we know the win probabilities between every pair of players: the probability that player $A$ defeats player $B$ is $P_{A,B}$ (guaranteed that $P_{A,B}+P_{B,A}=1$). Student Z hopes to determine the matchups (reassign positions for all players) so that he can obtain as much prize money as possible in expectation. Can you help Student Z find an arrangement that maximizes his expected prize?

Input Format

This is an output-only problem. All input files match*.in are provided in the additional files.

The first line of match*.in contains a positive integer $n$, the total number of participants. The data guarantees that there exists a non-negative integer $k$ such that $2^k=n$.

Next come $n$ lines, each containing $n$ real numbers between $0$ and $1$, $P_{i,j}$, meaning the probability that player with ID $i$ defeats player with ID $j$. Each real number is given to two digits after the decimal point. Note in particular that $P_{i,i}=0.00$.

Next come $k+1$ lines, each containing one integer, giving the prizes for different rounds of advancement. The value on line $i$ is $a_i$.

Output Format

The output file match*.out contains $n$ lines. The number on line $i$ is the ID of the student placed at position $i$. Student Z’s ID must be placed at position $1$.

4
0.00 0.70 0.60 0.80
0.30 0.00 0.60 0.40
0.40 0.40 0.00 0.70
0.20 0.60 0.30 0.00
1
2
3

1
4
2
3

Hint

Sample Explanation

After the first round, the probability that the player with ID $1$ (Student Z) advances is $80\%$, the probability that the player with ID $2$ advances is $60\%$, the probability that the player with ID $3$ advances is $40\%$, and the probability that the player with ID $4$ advances is $20\%$.

In the second round (the final), the probability that player $1$ (Student Z) wins both rounds is $80\%\times (60\%\times 70\%+40\%\times 60\%)=52.8\%$. Therefore, the probability that Student Z loses in the first round is $P_1=1-0.8=0.2$, the probability that he wins the first round but loses in the second round is $P_2=0.8-0.528=0.272$, and the probability that he becomes the champion is $P_3=0.528$.

Thus, the expected prize is $0.2\times 1+(0.8-0.528)\times 2+0.528\times 3=2.328$.

How to Test Your Output

We provide checker to test whether your output file is acceptable.

After calling this program, checker will give the result based on your output file, including:

• Abnormal termination: unknown error.
• Format error: output file format error.
• Not a permutation: the output file is not a permutation of $1\sim n$.
• OK.Your answer is xxx: the output file is accepted, and xxx is the corresponding expected prize.

Scoring Method

Each test point is scored independently.

For each test point, if your output file is invalid (such as wrong format, or the output does not meet the requirements), you get $0$ points for that test point. Otherwise, let your expected prize be $\text{your\_ans}$, and the reference expected prize be $\text{our\_ans}$. We also have a scoring parameter $d$. Your score for that test point is as follows:

• If $\text{your\_ans}>\text{our\_ans}$, you get $12$ points.
• If $\text{your\_ans}<\text{our\_ans}\times d$, you get $1$ point.
• Otherwise, the score is:$$\left\lfloor\frac{\text{your\_ans}-\text{our\_ans}\times d}{\text{our\_ans}-\text{our\_ans}\times d}\times 8\right\rfloor+2$$

Special Note

Please keep the input files *.in and your outputs *.out properly, and back them up in time to avoid accidental deletion.

Additional Files

You need to compile and use checker by yourself.

Please go to Github to download the latest source code of testlib.h.

Translated by ChatGPT 5