I hate Matrix Construction

AtCoder

IDabc164_f

Time2000ms

Memory256MB

Difficulty—

Given are an integer $N$ and arrays $S$, $T$, $U$, and $V$, each of length $N$. Construct an $N×N$ matrix $a$ that satisfy the following conditions: * $a_{i,j}$ is an integer. * $0 \leq a_{i,j} \lt 2^{64}$. * If $S_{i} = 0$, the bitwise AND of the elements in the $i$\-th row is $U_{i}$. * If $S_{i} = 1$, the bitwise OR of the elements in the $i$\-th row is $U_{i}$. * If $T_{i} = 0$, the bitwise AND of the elements in the $i$\-th column is $V_{i}$. * If $T_{i} = 1$, the bitwise OR of the elements in the $i$\-th column is $V_{i}$. However, there may be cases where no matrix satisfies the conditions. ## Constraints * All values in input are integers. * $1 \leq N \leq 500$ * $0 \leq S_{i} \leq 1$ * $0 \leq T_{i} \leq 1$ * $0 \leq U_{i} \lt 2^{64}$ * $0 \leq V_{i} \lt 2^{64}$ ## Input Input is given from Standard Input in the following format: $N$ $S_{1}$ $S_{2}$ $...$ $S_{N}$ $T_{1}$ $T_{2}$ $...$ $T_{N}$ $U_{1}$ $U_{2}$ $...$ $U_{N}$ $V_{1}$ $V_{2}$ $...$ $V_{N}$ [samples]

Samples

Input #1

Output #1

1 1
1 0

In Sample Input $1$, we need to find a matrix such that:

*   the bitwise AND of the elements in the $1$\-st row is $1$;
*   the bitwise OR of the elements in the $2$\-nd row is $1$;
*   the bitwise OR of the elements in the $1$\-st column is $1$;
*   the bitwise AND of the elements in the $2$\-nd column is $0$.

Input #2

Output #2

15 11
15 11

API Response (JSON)

{
  "problem": {
    "name": "I hate Matrix Construction",
    "description": {
      "content": "Given are an integer $N$ and arrays $S$, $T$, $U$, and $V$, each of length $N$. Construct an $N×N$ matrix $a$ that satisfy the following conditions: *   $a_{i,j}$ is an integer. *   $0 \\leq a_{i,j} \\",
      "description_type": "Markdown"
    },
    "platform": "AtCoder",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "abc164_f"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "Given are an integer $N$ and arrays $S$, $T$, $U$, and $V$, each of length $N$. Construct an $N×N$ matrix $a$ that satisfy the following conditions:\n\n*   $a_{i,j}$ is an integer.\n*   $0 \\leq a_{i,j} \\...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments