← 返回题目列表

Codeforces · 2038/I

I. 多项全能

中文机器翻译题面 查看原题

贝尔兰是今年国际大学生全能比赛的主办国!与冬季两项是两项运动的比赛类似,全能是多种运动的比赛。今年,有 $$$m$$$ 体育项目。此外,该活动还有 $$$n$$$ 参与者。运动项目编号从$$$1$$$到$$$m$$$,参与者编号从$$$1$$$到$$$n$$$。

一些参与者精通多种运动。给定一个二进制矩阵 $$$n \times m$$$,如果第 $$$i$$$ 个参与者擅长第 $$$j$$$ 项运动,则第 $$$i$$$ 行的第 $$$j$$$ 个字符为 1,否则为 0。还已知,对于每对参与者,至少存在一项运动,使得其中一个擅长该运动,而另一个则不擅长。

比赛项目顺序在开幕式上确定。从历史上看,这是由全能的随机数生成器完成的。滚动从 $$$1$$$ 到 $$$m$$$ 的随机数 $$$x$$$。然后,比赛从运动项目 $$$x$$$ 开始,然后进行运动项目 $$$(x \bmod m + 1)$$$,然后进行运动项目 $$$((x + 1) \bmod m + 1)$$$,依此类推。

每项运动的进行如下。如果所有剩余的参赛者(所有尚未被淘汰的参赛者)都不擅长该项目,则每个人都会进入下一项项目。否则,所有熟练的参赛者将进入下一项比赛,所有不熟练的参赛者将被淘汰出局。一旦比赛中只剩下一名参赛者,比赛就会结束,该参赛者将被宣布为获胜者。

作为比赛的组织者,你事先很好奇比赛可能出现的结果(不是说你要随机掷骰子,你怎么可能会这样想……)。对于每项运动 $$$x$$$,如果比赛以运动 $$$x$$$ 开始,则打印获胜者的索引。

输入

第一行包含两个整数 $$$n$$$ 和 $$$m$$$ ($$$2 \le n, m \le 10^6$$$; $$$n \le 2^m$$$; $$$nm \le 2 \cdot 10^6$$$) – 分别是参与者人数和运动项目数量。

接下来的 $$$n$$$ 行中的第 $$$i$$$ 行包含一个二进制字符串,该字符串恰好由 $$$m$$$ 个字符 0 或 1 组成 - 第 $$$i$$$ 个参与者的技能组。如果第 $$$j$$$ 个字符为 1,则第 $$$i$$$ 个参与者擅长第 $$$j$$$ 项运动。如果为 0,则第 $$$i$$$ 参与者不擅长第 $$$j$$$ 运动。

对输入的附加约束:对于每对参与者,至少存在一项运动,其中一个人擅长该运动,而另一个则不擅长。换句话说,所有 $$$n$$$ 二进制字符串都是两两不同的。

输出

打印 $$$m$$$ 整数。对于从 $$$1$$$ 到 $$$m$$$ 的每个 $$$x$$$,如果比赛以 $$$x$$$ 运动开始,则打印获胜者的索引。

示例

输入 #1

3 5
10010
01100
10101

输出 #1

3 2 3 1 3