問題一覧 > 通常問題

No.2505 matriX cOnstRuction

レベル : / 実行時間制限 : 1ケース 2.500秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : （AC するまで非表示） / 解いたユーザー数 14
作問者 : suisen / テスター : emthrm torisasami4 rniya
お気に入りにしたユーザー ProblemId : 9088 / 自分の提出
問題文最終更新日: 2023-08-21 23:52:49
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Show the original
yukicoder contest 408 (順位表) の他の問題:

Problem Statement

You are given an $n\times m$ matrix $A=(a_{i,j})_{1\leq i\leq n,1\leq j \leq m}$, a sequence $R = ( R_1, R _ 2, \ldots, R _ n)$ of length $n$, and a sequence $C = (C _ 1, C _ 2, \ldots, C _ m)$ of length $m$.

Initially, all elements of the $n\times m$ matrix $B=(b_{i,j})_{1\leq i\leq n,1\leq j \leq m}$ are $0$. You can perform the following $2$ types of operations on $B$ any number of times in any order. In particular, you do not have to perform even $1$ operation. Below, $\oplus$ denotes bitwise XOR.

  • (Operation 1): Choose integers $i,x$ satisfying $1\leq i\leq n$ and $0\leq x\leq R_i$, and for every integer $j$ satisfying $1\leq j\leq m$, update $b_{i,j}\leftarrow b_{i,j}\oplus x$.
  • (Operation 2): Choose integers $j,x$ satisfying $1\leq j\leq m$ and $0\leq x\leq C_j$, and for every integer $i$ satisfying $1\leq i\leq n$, update $b_{i,j}\leftarrow b_{i,j}\oplus x$.

Your goal is to make $b_{i,j}=a_{i,j}$ hold for all integers $i,j$ satisfying $1\leq i\leq n,1\leq j\leq m$.

Determine whether this is possible, and if it is possible, find the minimum number of operations needed to achieve the goal.

$1$ file contains $T$ test cases; solve the above problem for all of them.

Input

The input is given from Standard Input in the following format.

$T$
$\mathrm{testcase} _ 1$
$\mathrm{testcase} _ 2$
$\vdots$
$\mathrm{testcase} _ T$

Here, $\mathrm{testcase} _ i\ (1\leq i\leq T)$ is the input for the $i$-th test case, given in the following format.

$n\ m$
$R _ 1\ R _ 2\ \cdots\ R _ n$
$C _ 1\ C _ 2\ \cdots\ C _ m$
$a _ {1, 1}\ a _ {1, 2}\ \cdots\ a _ {1, m}$
$a _ {2, 1}\ a _ {2, 2}\ \cdots\ a _ {2, m}$
$\vdots$
$a _ {n, 1}\ a _ {n, 2}\ \cdots\ a _ {n, m}$
  • All input values are integers.
  • $1\leq T\leq 5\times 10 ^ 4$
  • $1\leq n$
  • $1\leq m$
  • $nm \leq 5\times 10 ^ 4$
  • $0\leq R _ i \lt 2 ^ {30}$
  • $0\leq C _ i \lt 2 ^ {30}$
  • $0\leq a _ {i, j} \lt 2 ^ {30}$
  • The sum of $nm$ over the $T$ test cases is at most $5\times 10 ^ 4$.

Output

Output $T$ lines.

On line $i\ (1\leq i\leq T)$, for the $i$-th test case, output -1 if the goal cannot be achieved, and otherwise output the minimum number of operations.

Also output a newline after line $T$.

Sample

Sample 1
Input
3
3 3
3 2 1
3 2 3
1 1 1
0 0 0
2 2 2
2 3
3 5
1 2 3
1000 1000 1000
1000 1000 1000
2 1
3 4
5
0
0
Output
5
-1
0

This input consists of $3$ test cases.

  • Regarding the $1$st case:

    The input represents $n=3,\ m=3,\ R=(3,2,1),\ C=(3,2,3),\ A=\begin{pmatrix} 1 & 1 & 1 \newline 0 & 0 & 0 \newline 2 & 2 & 2 \end{pmatrix}$. For example, $B$ can be made equal to $A$ by the $5$ operations shown below.

    1. For all $j=1,\ldots,m$, set $b _ {1, j} \leftarrow b _ {1, j} \oplus 3$. As a result of this operation, $B=\begin{pmatrix} 3 & 3 & 3 \newline 0 & 0 & 0 \newline 0 & 0 & 0 \end{pmatrix}$. Here, $0\leq 3\leq R _ 1$ indeed holds.
    2. For all $i=1,\ldots,n$, set $b _ {i, 2} \leftarrow b _ {i, 2} \oplus 2$. As a result of this operation, $B=\begin{pmatrix} 3 & 1 & 3 \newline 0 & 2 & 0 \newline 0 & 2 & 0 \end{pmatrix}$. Here, $0\leq 2\leq C _ 2$ indeed holds.
    3. For all $j=1,\ldots,m$, set $b _ {2, j} \leftarrow b _ {2, j} \oplus 2$. As a result of this operation, $B=\begin{pmatrix} 3 & 1 & 3 \newline 2 & 0 & 2 \newline 0 & 2 & 0 \end{pmatrix}$. Here, $0\leq 2\leq R _ 2$ indeed holds.
    4. For all $i=1,\ldots,n$, set $b _ {i, 1} \leftarrow b _ {i, 1} \oplus 2$. As a result of this operation, $B=\begin{pmatrix} 1 & 1 & 3 \newline 0 & 0 & 2 \newline 2 & 2 & 0 \end{pmatrix}$. Here, $0\leq 2\leq C _ 1$ indeed holds.
    5. For all $i=1,\ldots,n$, set $b _ {i, 3} \leftarrow b _ {i, 3} \oplus 2$. As a result of this operation, $B=\begin{pmatrix} 1 & 1 & 1 \newline 0 & 0 & 0 \newline 2 & 2 & 2 \end{pmatrix}$. Here, $0\leq 2\leq C _ 3$ indeed holds.

    It can be proved that $B$ cannot be made equal to $A$ with fewer than $5$ operations. Therefore, output $5$ as the answer for this case.

  • Regarding the $2$nd case:

    No matter how the operations are performed, $B$ cannot be made equal to $A$, so output -1.

  • Regarding the $3$rd case:

    $B$ is equal to $A$ from the beginning. Therefore, the minimum number of operations is $0$.

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。