CF1523D Love-Hate

William 正在为他的 $n$ 位交易员朋友举办一场聚会。他们开始讨论各种他们交易的货币，但有一个问题：并不是所有的朋友都喜欢每一种货币。他们只喜欢其中的一些货币，不喜欢其他的。 对于 William 的每一位朋友 $i$，已知他是否喜欢货币 $j$。总共有 $m$ 种货币。还已知每位交易员最多只会喜欢 $p$ 种货币。 由于朋友们需要有共同的话题进行讨论，他们需要找到一个最大基数（可以为空）的货币子集，使得至少有 $ \lceil \frac{n}{2} \rceil $ 位朋友（向上取整）喜欢该子集中的每一种货币。

第一行包含三个整数 $n, m, p$，分别表示交易员朋友的数量、货币的数量以及每位朋友最多喜欢的货币数量，满足 $1 \le n \le 2 \cdot 10^5, 1 \le p \le m \le 60, 1 \le p \le 15$。 接下来的 $n$ 行，每行包含 $m$ 个字符。第 $i$ 行的第 $j$ 个字符为 $1$ 表示第 $i$ 位朋友喜欢第 $j$ 种货币，为 $0$ 表示不喜欢。保证每行中 $1$ 的数量不超过 $p$。

输出一个长度为 $m$ 的字符串，表示最大规模的货币子集，其中被选中的货币用字符 $1$ 表示。 如果有多种答案，输出任意一种即可。

在第一个样例中，只有第一种货币被至少 $ \lceil \frac{3}{2} \rceil = 2 $ 位朋友喜欢，因此很容易证明无法找到更优的答案。 在第二个样例中，答案包含 $2$ 种货币，并且会被第 $1$、$2$ 和 $5$ 位朋友喜欢。对于本样例，还有其他被至少一半朋友喜欢的货币，但使用它们无法得到更大的子集。 由 ChatGPT 4.1 翻译