CF486B.OR in Matrix

普及-

通过率:0%

时间限制:1.00s

内存限制:256MB

AC君温馨提醒

该题目为【codeforces】题库的题目,您提交的代码将被提交至codeforces进行远程评测,并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供,我们无法保证该服务的稳定性,若提交后无反应,请等待一段时间后再进行重试。

题目描述

Let's define logical OR as an operation on two logical values (i. e. values that belong to the set {0, 1}) that is equal to 1 if either or both of the logical values is set to 1, otherwise it is 0. We can define logical OR of three or more logical values in the same manner:

where is equal to 1 if some a__i = 1, otherwise it is equal to 0.

Nam has a matrix A consisting of m rows and n columns. The rows are numbered from 1 to m, columns are numbered from 1 to n. Element at row i (1 ≤ i ≤ m) and column j (1 ≤ j ≤ n) is denoted as A__ij. All elements of A are either 0 or 1. From matrix A, Nam creates another matrix B of the same size using formula:

.

(B__ij is OR of all elements in row i and column j of matrix A)

Nam gives you matrix B and challenges you to guess matrix A. Although Nam is smart, he could probably make a mistake while calculating matrix B, since size of A can be large.

我们定义逻辑 OR(或运算)为作用于两个逻辑值(即属于集合 {0, 1}\{0, 1\} 的值)上的运算:当且仅当两个逻辑值中至少有一个为 11 时,结果为 11;否则结果为 00。类似地,我们可以将逻辑 OR 扩展到三个或更多逻辑值:


其中 在某个 ai=1a_i = 1 时等于 11,否则等于 00。

Nam 拥有一个由 mm 行和 nn 列组成的矩阵 AA。行编号从 11 到 mm,列编号从 11 到 nn。位于第 ii 行(1 ≤ i ≤ m1 ≤ i ≤ m)和第 jj 列(1 ≤ j ≤ n1 ≤ j ≤ n)的元素记为 AijA_{ij}。矩阵 AA 中所有元素均为 00 或 11。Nam 根据矩阵 AA 构造另一个同尺寸的矩阵 BB,其定义如下:

。

(即 BijB_{ij} 是矩阵 AA 中第 ii 行与第 jj 列所有元素的逻辑 OR)

Nam 给出矩阵 BB,并挑战你反推出矩阵 AA。尽管 Nam 很聪明,但由于矩阵 AA 的尺寸可能很大,他在计算矩阵 BB 时仍有可能出错。

输入格式

The first line contains two integer m and n (1 ≤ m, n ≤ 100), number of rows and number of columns of matrices respectively.

The next m lines each contain n integers separated by spaces describing rows of matrix B (each element of B is either 0 or 1).

第一行包含两个整数 mm 和 nn(1≤m,n≤1001 \leq m, n \leq 100),分别表示矩阵的行数和列数。

接下来的 mm 行,每行包含 nn 个用空格分隔的整数,描述矩阵 BB 的各行(BB 的每个元素为 00 或 11)。

输出格式

In the first line, print "NO" if Nam has made a mistake when calculating B, otherwise print "YES". If the first line is "YES", then also print m rows consisting of n integers representing matrix A that can produce given matrix B. If there are several solutions print any one.

第一行,如果 Nam 在计算矩阵 BB 时出错,则输出 "NO";否则输出 "YES"。若第一行输出为 "YES",则还需输出 mm 行,每行包含 nn 个整数,表示一个能生成给定矩阵 BB 的矩阵 AA。若存在多个解,输出任意一个即可。

输入输出样例

  • 输入#1

    2 2
    1 0
    0 0

    输出#1

    NO
  • 输入#2

    2 3
    1 1 1
    1 1 1

    输出#2

    YES
    1 1 1
    1 1 1
  • 输入#3

    2 3
    0 1 0
    1 1 1

    输出#3

    YES
    0 0 0
    0 1 0

输入解题思路,AI测评打分。不知道怎么写?

首页