P9786 [ROIR 2020] 机器人锦标赛 (Day1)

**译自 [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)，译者 alpha1022*** 机器人高速布尔函数计算锦标赛的任务由评委会准备。 机器人的一个任务是一张 $m$ 行 $n$ 列的表格，其中每个格子有一个整数权值，且记第 $i$ 行 $j$ 列的格子的权值为 $x_{i,j}$。 对于每一列，该列中所有格子的权值组成了一个 $0\ldots m-1$ 的排列。换句话说，每列中所有格子的权值互不相同： 若 $i \ne k$，则对于所有的 $j$ 有 $x_{i,j} \ne x_{k,j}$，且有 $0 \le x_{i,j} < m$。 对于每一列，评委会设置了一个阈值 —— 一个在 $[0,m]$ 内的非负整数 $z_j$。你需要以所有形如 $x_{i,j} < z_j$ 的逻辑表达式的值为参数计算布尔函数的值。一个逻辑表达式的值为 $1$ 当且仅当这个表达式成立，否则为 $0$。 在比赛中，选手们需要计算 $m$ 个布尔函数的值 —— 对每一行计算一次。每个布尔函数以一个**非重复单调线性规划**（NMLP）定义。 考虑第 $i$ 行的 NMLP。 这是由 $n-1$ 条以 $1 \ldots n-1$ 编号的指令组成的一个序列，第 $p$ 条指令给定三个数：$a_p, b_p, op_p$。$op_p$ 只有两种取值：$1$ 表示与运算，$2$ 表示或运算。 而 $a_p,b_p$ 则是第 $p$ 个指令的参数，满足 $1 \le a_p,b_p < n+p$。 考虑一个仅包含 $0$ 和 $1$ 的数组 $val[1\ldots 2n-1]$。对于 $1 \le j \le n$，$val[j] = [x_{i,j} < z_j]$，其中 $[P]$ 表示表达式 $P$ 的值。 而 $val[n+p]$ 的值通过第 $p$ 条指令计算。 - 对于 $op_p = 1$，$val[n+p] = (val[a_p]\ \texttt{and}\ val[b_p])$。 - 对于 $op_p = 2$，$val[n+p] = (val[a_p]\ \texttt{or}\ val[b_p])$。 该规划是非重复的，也就是说，对于 $p = 1\ldots n-1$，所有 $2n-2$ 个 $a_p,b_p$ 的值互不相同。 程序执行的结果即为 $val[2n-1]$。 目前评委会已经准备好了所有的 $x_{i,j}$，需要由你来确定每一列的阈值才能完整地准备这个任务。 评委会认为一个任务是平衡的，当且仅当所有 $m$ 行中恰有 $s$ 行的布尔函数最后得到的结果为 $1$，其余 $m-s$ 行得到 $0$。 你的任务即为替评委会找到合适的阈值。 对于此题，可以证明一定存在至少一种选择阈值的方案满足上述条件。

第一行，三个整数 $n,m,s$。 以下 $m(n-1)$ 行，第 $i \cdot (n-1) + p\;(1 \le p \le n-1)$ 行包含三个整数 $a_p,b_p,op_p$，表示第 $i$ 行的第 $p$ 个操作。 以下 $m$ 行，每行 $n$ 个整数，表示所有的 $x_{i,j}$。

输出 $n$ 个整数 $z_1, z_2, \ldots, z_n\;(0 \le z_j \le m)$。 如有多解，任意输出一个即可。

#### 【样例解释】 在此样例中共有 $3$ 行，你需要令其中恰好两行的函数值为 $1$，另一行的函数值为 $0$。 让我们看看第一行的 $val$ 数组是什么样的。 前四个值通过格子中的权值和阈值计算： - $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$。 接下来，对第一行执行线性规划： - $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$。 因此，第一行的函数值为 $0$。 顺带一提，若我们整理一下这些式子，可得： $$ [((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))] $$ 类似地，第二行和第三行的函数值分别为 $$ [(((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)] $$ 和 $$ [((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))] $$ 当我们令 $z_1 = 0,z_2 = 1,z_3 = 2,z_4 = 3$ 时，我们可以得到以下表达式： 第二行： $$ [(((2 < 0)\ \texttt{or}\ (2 < 1))\ \texttt{and}\ (1 < 2))\ \texttt{or}\ (0 < 3)] = 1 $$ 第三行： $$ [((1 < 0)\ \texttt{and}\ (1 < 3))\ \texttt{or}\ ((0 < 1)\ \texttt{and}\ (0 < 2))] = 1 $$ 请注意这不是唯一的解，可行的解还包括 $z_1 = 0, z_2 = 0, z_3 = 3, z_4 = 3$。 #### 【数据范围】 对于 $100\%$ 的数据，$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$。 具体数据限制如下表： |子任务编号|限制|分值| |:-:|:-:|:-:| |$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$|每一行的 NMLP 相同|$10$| |$8$|-|$30$|