P9786 [ROIR 2020] Robot Championship (Day1)

**Translated from [ROIR 2020](http://neerc.ifmo.ru/school/archive/2019-2020.html) Day1 T4.** ***[Олимпиада для роботов ](http://neerc.ifmo.ru/school/archive/2019-2020/ru-olymp-regional-2020-day1.pdf), translator alpha1022.*** The jury has prepared tasks for the Robot High-Speed Boolean Function Computation Championship. One task for the robots is a table with $m$ rows and $n$ columns, where each cell has an integer weight. Denote the weight in row $i$ and column $j$ by $x_{i,j}$. For each column, the weights of all cells in that column form a permutation of $0 \ldots m-1$. In other words, all weights in each column are pairwise distinct: if $i \ne k$, then for all $j$ we have $x_{i,j} \ne x_{k,j}$, and $0 \le x_{i,j} < m$. For each column, the jury sets a threshold: a non-negative integer $z_j$ in $[0,m]$. You need to compute the value of a Boolean function using the values of all logical expressions of the form $x_{i,j} < z_j$ as inputs. A logical expression has value $1$ if and only if it is true, otherwise it is $0$. In the contest, participants need to compute values of $m$ Boolean functions, one for each row. Each Boolean function is defined by a **Non-repeating Monotone Linear Program** (NMLP). Consider the NMLP for row $i$. It is a sequence of $n-1$ instructions numbered from $1 \ldots n-1$. Instruction $p$ is given by three numbers: $a_p$, $b_p$, $op_p$. The value of $op_p$ has only two possibilities: $1$ means AND, $2$ means OR. The parameters $a_p, b_p$ satisfy $1 \le a_p, b_p < n+p$. Consider an array $val[1\ldots 2n-1]$ containing only $0$ and $1$. For $1 \le j \le n$, $val[j] = [x_{i,j} < z_j]$, where $[P]$ denotes the value of expression $P$. The value of $val[n+p]$ is computed using instruction $p$: - If $op_p = 1$, then $val[n+p] = (val[a_p]\ \texttt{and}\ val[b_p])$. - If $op_p = 2$, then $val[n+p] = (val[a_p]\ \texttt{or}\ val[b_p])$. The program is non-repeating, meaning that for $p = 1\ldots n-1$, all the $2n-2$ values among $a_p, b_p$ are pairwise distinct. The result of executing the program is $val[2n-1]$. The jury has already prepared all $x_{i,j}$, and you need to determine the thresholds for each column to complete the task setup. The jury considers a task balanced if and only if among all $m$ rows, exactly $s$ rows have final Boolean function value $1$, and the remaining $m-s$ rows have value $0$. Your task is to find suitable thresholds for the jury. For this problem, it can be proven that there exists at least one choice of thresholds satisfying the above condition.

The first line contains three integers $n, m, s$. The next $m(n-1)$ lines describe the operations. Line $i \cdot (n-1) + p$ ($1 \le p \le n-1$) contains three integers $a_p, b_p, op_p$, representing the $p$-th operation of row $i$. The next $m$ lines each contain $n$ integers, describing all $x_{i,j}$.

Output $n$ integers $z_1, z_2, \ldots, z_n$ ($0 \le z_j \le m$). If there are multiple solutions, output any one.

#### Sample Explanation In this sample there are $3$ rows. You need to make exactly two rows have function value $1$, and the other row have function value $0$. Let us see what the $val$ array looks like for the first row. The first four values are computed from the cell weights and the thresholds: - $val[1] = [x_{1,1} < z_1] = [0 < 0] = 0$. - $val[2] = [x_{1,2} < z_2] = [1 < 1] = 0$. - $val[3] = [x_{1,3} < z_3] = [2 < 2] = 0$. - $val[4] = [x_{1,4} < z_4] = [2 < 3] = 1$. Next, execute the linear program for the first row: - $val[5] = (val[1]\ \texttt{and}\ val[2]) = (0\ \texttt{and}\ 0) = 0$. - $val[6] = (val[3]\ \texttt{and}\ val[4]) = (0\ \texttt{and}\ 1) = 0$. - $val[7] = (val[5]\ \texttt{or}\ val[6]) = (0\ \texttt{or}\ 0) = 0$. Therefore, the function value of the first row is $0$. By the way, if we rewrite these expressions, we get: $$ [((x_{1,1} < z_1)\ \texttt{and}\ (x_{1,2} < z_2))\ \texttt{or}\ ((x_{1,3} < z_3)\ \texttt{and}\ (x_{1,4} < z_4))] $$ Similarly, the function values of the second and third rows are: $$ [(((x_{2,1} < z_1)\ \texttt{or}\ (x_{2,2} < z_2))\ \texttt{and}\ (x_{2,3} < z_3))\ \texttt{or}\ (x_{2,4} < z_4)] $$ and $$ [((x_{3,1} < z_1)\ \texttt{and}\ (x_{3,4} < z_4))\ \texttt{or}\ ((x_{3,2} < z_2)\ \texttt{and}\ (x_{3,3} < z_3))] $$ When we set $z_1 = 0, z_2 = 1, z_3 = 2, z_4 = 3$, we get the following expressions: Second row: $$ [(((2 < 0)\ \texttt{or}\ (2 < 1))\ \texttt{and}\ (1 < 2))\ \texttt{or}\ (0 < 3)] = 1 $$ Third row: $$ [((1 < 0)\ \texttt{and}\ (1 < 3))\ \texttt{or}\ ((0 < 1)\ \texttt{and}\ (0 < 2))] = 1 $$ Note that this is not the only solution. Other feasible solutions include $z_1 = 0, z_2 = 0, z_3 = 3, z_4 = 3$. #### Constraints For $100\%$ of the testdata: $1 \le n, m \le 3 \cdot 10^5$, $n \cdot m \le 3 \cdot 10^5$, $0 \le s \le m$, $1 \le a_p, b_p \le n+p$, $0 \le x_{i,j} < m$. The detailed limits are shown in the table below: |Subtask ID|Limit|Points| |:-:|:-:|:-:| |$1$|$n \le 2, m \le 10^3$|$10$| |$2$|$n \le 2, m \le 10^5$|$10$| |$3$|$n \le 10, m \le 2$|$10$| |$4$|$x_{i,j} = i-1$|$5$| |$5$|$op_p = 1$|$5$| |$6$|$n \le 100$|$20$| |$7$|The NMLP is the same for every row.|$10$| |$8$|-|$30$| Translated by ChatGPT 5