P4249 [WC2007] Rock-Paper-Scissors

In some one-on-one game competitions (such as chess, table tennis, and badminton singles), we often encounter the interesting situation where $A$ beats $B$, $B$ beats $C$, and $C$ beats $A$. Let us vividly call this the rock-paper-scissors situation. Sometimes, people will enthusiastically count how many such rock-paper-scissors situations occur, that is, how many unordered triples $(A, B, C)$ satisfy that one person beats another, the second beats the third, and the third beats the first. Note that unordered means the order of elements in the triple does not matter, and $(A, B, C)$, $(A, C, B)$, $(B, A, C)$, $(B, C, A)$, $(C, A, B)$, and $(C, B, A)$ are regarded as the same situation. There are $N$ people participating in such a competition. The schedule requires that every pair of people plays exactly one match, so there are a total of $\frac{N*(N-1)}{2}$ matches. Some matches have already been played. We want to know, in the extreme case, what is the maximum possible number of rock-paper-scissors situations after all matches are completed. That is, given the results of the matches that have already taken place, you may assign the outcomes of the remaining matches arbitrarily to obtain as many rock-paper-scissors situations as possible.

The first line contains an integer $N$, the number of participants. Then follows an $N$-by-$N$ numeric matrix: $N$ rows, each with $N$ columns, and numbers separated by spaces. In row $(i+1)$ and column $j$, if the number is $1$, it means $i$ has already beaten $j$; if the number is $0$, it means $i$ has already lost to $j$; if the number is $2$, it means the match between $i$ and $j$ has not yet taken place. The numbers on the diagonal, i.e., the number in row $(i+1)$ and column $i$, are all $0$. They are merely placeholders and have no meaning. The input is guaranteed to be valid and without contradictions. When $i \neq j$, the two numbers at row $(i+1)$, column $j$ and row $(j+1)$, column $i$ are either both $2$, or one is $0$ and the other is $1$.

The first line contains an integer, indicating how many rock-paper-scissors situations occur in your arranged set of match results. Starting from line $2$, output an $N$-by-$N$ numeric matrix in the same format as the input. The number in row $(i+1)$ and column $j$ describes the result of the match between $i$ and $j$: $1$ means $i$ beats $j$, and $0$ means $i$ loses to $j$. Unlike the input matrix, there is no number $2$ indicating an unplayed match; the diagonal numbers are all $0$. The output matrix must be valid and free of contradictions.

- Scoring criteria: For each test point, you will receive full credit only if the first line of your output matches the standard answer and you provide a valid arrangement consistent with it. Otherwise, you will receive $0$ points for that test point. - Constraints: For $30\%$ of the testdata, $N \leq 6$. For $100\%$ of the testdata, $N \leq 100$. Translated by ChatGPT 5