P14863 [ICPC 2021 Yokohama R] Distributing the Treasure

你是一个寻宝团队的队长。在你的英明领导下，你的团队在一次探险中取得了巨大成功，获得了大量宝藏。唯一但至关重要的剩余问题是如何将这些获得的宝藏分配给团队成员。 挖掘出的宝藏包括各种珍贵物品：金条、镶嵌璀璨宝石的珠宝、精美的工艺品等等。每位团队成员各自估计这些物品的价值。这些估值是一致的，也就是说，对于任意两个物品，如果某位成员估计其中一个严格高于另一个，则没有成员会给出相反的估计，尽管有些人可能给出相等的估值。 所有成员都是理智的，因此理解均匀分配物品的困难。因此，没有成员会仅仅因为基于其自己的估值，其所获份额的价值总和低于另一位成员的份额而抱怨。然而，如果他们的份额与某些其他成员的份额相比显得不合理地寒酸，他们可能会生气；他们无法忍受的是，即使在舍弃另一位成员份额中估值最低的一件物品后，自己份额的估值仍然严格低于那位成员的份额。 你作为队长的最后任务是决定谁获得哪些物品，以使没有成员生气。只要不生气，有些成员可能什么也得不到。

输入由单个测试用例组成，格式如下。 $$ \begin{aligned} &n\ m \\ &v_{1,1}\ \cdots\ v_{1,m} \\ &\vdots \\ &v_{n,1}\ \cdots\ v_{n,m} \end{aligned} $$ 输入的第一行有两个正整数 $n$ 和 $m$，其乘积不超过 $2 \times 10^5$；$n$ 是你的寻宝团队的成员数量，$m$ 是宝藏物品的数量。成员和物品分别编号为 $1$ 到 $n$ 和 $1$ 到 $m$。接下来的 $n$ 行中，第 $i$ 行有 $m$ 个不超过 $2 \times 10^5$ 的正整数，按降序排列：$v_{i,1} \geq v_{i,2} \geq \cdots \geq v_{i,m}$。这里，$v_{i,j}$ 是成员 $i$ 对物品 $j$ 的估值。

如果你可以在不让任何成员生气的情况下将物品分配给成员，则在一行中输出这样的分配，为 $m$ 个正整数 $x_1, x_2, \dots, x_m$，用空格分隔。这里，$x_j = i$ 表示成员 $i$ 获得物品 $j$。如果存在两个或更多这样的分配，其中任意一个都将被视为正确。如果无法在不惹怒任何成员的情况下分配物品，则只需在一行中输出 $0$。

令 $V_i(X)$ 表示成员 $i$ 对集合 $X$ 中物品价值的估值总和。 在样例 1 中，$V_1(\{1,3\})$ 是 $4 + 1 = 5$，$V_1(\{2\})$ 是 $2$，$V_2(\{1,3\})$ 是 $3 + 3 = 6$，$V_2(\{2\})$ 是 $3$。输出所示的分配不会让成员 $1$ 生气，因为 $V_1(\{1,3\}) \geq V_1(\{2\})$。即使 $V_2(\{2\}) < V_2(\{1,3\})$ 成立，成员 $2$ 也不会生气。如果成员 $1$ 放弃两件物品中的一件，那么成员 $1$ 获得的物品价值总和将变为 $V_2(\{1\}) = 3$ 或 $V_2(\{3\}) = 3$，两者均不高于 $V_2(\{2\}) = 3$。 注意，他们的份额不应交换。假设成员 $1$ 获得 $\{2\}$，成员 $2$ 获得 $\{1,3\}$。这会让成员 $1$ 生气，因为 $V_1(\{2\}) = 2 < 4 = V_1(\{1\})$ 成立，这意味着即使成员 $2$ 舍弃物品 $3$（这是 $\{1,3\}$ 中估值较低的一件），剩余的唯一物品 $1$ 的价值仍然被估值高于 $V_1(\{2\}) = 2$。 在样例 2 中，你是团队的唯一成员，因此你可以全部拿走。恭喜！ 翻译由 DeepSeek V3 完成