题目描述

一次，s1mple 找到了著名的问题解决者 Kostya，对他说：

如果你想变得更强，就需要持续练习。这里有一个用于训练的问题：

给定一个大小为 $n \times m$ 的矩阵 $a$（$n$ 为行数，$m$ 为列数），其中每个元素要么是 $0$，要么是 $1$。已知每列恰好包含 $c_i$ 个 $1$。每列内的元素可以自由排列。目标是最大化包含奇数个 $1$ 的行数，并找出这样的一个矩阵。

Kostya 默默点头，坐到桌边开始工作，深知每一次练习都让他更接近精通。

Kostya 没能解决这个问题，现在请你帮他解决它。

如果你只找出数量而不输出矩阵，可以获得部分分数。详情见下文。

输入格式

• 第一行包含两个整数 $n$ 和 $m$（$1 \le n \cdot m \le 10^6$）——矩阵的维度。
• 第二行包含 $m$ 个整数 $c_1, c_2, \dots, c_m$（$0 \le c_i \le n$）——每列中 $1$ 的数量。

输出格式

• 第一行输出一个整数 $t$（$0 \leq t \leq n$）——矩阵中具有奇数和的行数。
• 接下来的 $n$ 行，每行输出 $m$ 个整数 $a_{ij}$（$0 \leq a_{ij} \leq 1$）——矩阵的元素。

8 4
6 1 6 1

6
1 1 1 0 
1 0 1 1 
1 0 1 0 
1 0 1 0 
1 0 0 0 
1 0 0 0 
0 0 1 0 
0 0 1 0 

4 4
3 0 3 0

2
1 0 1 0 
1 0 1 0 
1 0 0 0 
0 0 1 0 

7 3
4 3 2

7
1 1 1 
1 0 0 
1 0 0 
1 0 0 
0 1 0 
0 1 0 
0 0 1 

提示

在第一个示例中，第一列和第三列至少在 $4$ 个位置相交，这意味着如果只有这两列，我们将有 $4$ 个偶数和行。但由于还有两列各有一个 $1$，我们可以将其中两行转换为奇数和，因此最优答案是 $6$ 个奇数和行。

在第二个示例中，我们可以忽略第二列和第四列，因为它们没有 $1$，这意味着它们不会改变任何行的奇偶性。第一列和第三列至少在 $2$ 行相交，意味着至少有 $2$ 行是偶数和，因此答案是 $2$。

在第三个示例中，答案是 $7$，因为存在一个满足条件且具有 $7$ 个奇数和行的矩阵，并且不存在多于 $7$ 个奇数和行的矩阵。

评分细则

• （$10$ 分）：$n, m \le 5$；
• （$8$ 分）：矩阵中 $1$ 的总数不超过 $n$；
• （$20$ 分）：每列中 $1$ 的数量不超过 $n/2$；
• （$14$ 分）：$n, m \le 50$；
• （$14$ 分）：$n \le 3\,000$；
• （$14$ 分）：$n \cdot m \le 3\cdot10^5$；
• （$20$ 分）：无额外限制。

对于每个测试组，如果你为该组中每个测试输出了正确的 $t$，你可以获得该组一半的分数。

注意，要获得部分分数，你需要输出正确的 $t$ 并且：

• 要么不输出其他内容，即只输出 $t$，不输出矩阵；
• 要么输出一个完整的由 $0$ 和 $1$ 组成的矩阵，该矩阵不必正确。例如，可以是一个全零矩阵。

如果你只输出部分行、或输出过多行、或输出非 $0$ 非 $1$ 的数字等，你将获得 $0$ 分。

翻译由 DeepSeek V3 完成