No.2702 Nand Nor Matrix
タグ : / 解いたユーザー数 28
作問者 :
hamamu
Magentor
Problem Statement
In this problem, for $x,y\in \{0,1\}$, the functions $\text{nand}(x,y),\text{nor}(x,y)$ are defined as follows.
$\text{nand}(x,y)=\begin{cases}0\ (x=1 \land y=1)\\1\ (\text{otherwise.})\end{cases}$
$\text{nor}(x,y)=\begin{cases}1\ (x=0 \land y=0)\\0\ (\text{otherwise.})\end{cases}$
Haruku received an $N\times N$ matrix $X$ in which every element is $0$ or $1$. The elements of this matrix change as time passes.
More precisely, let $X_{t,i,j}$ be the element of $X$ at time $t$ in the $i$-th row from the top and the $j$-th column from the left. Then $X_{t,i,j}$ is determined by the following rules.
$X_{t,i,j}=\begin{cases}A_j\ (t=0\land i=1)\\B_i\ (t=0\land i\ne 1 \land j=1)\\0\ (t=0\land i\ne 1 \land j\ne 1)\\X_{t-1,i,j}\ (t>0\land (i=1\lor j=1))\\\text{nand}(X_{t-1,i-1,j},X_{t-1,i,j-1})\ (t>0 \land i\ne 1\land j\ne 1\land X_{t-1,i,j}=0)\\\text{nor}(X_{t-1,i-1,j},X_{t-1,i,j-1})\ (t>0 \land i\ne 1\land j\ne 1\land X_{t-1,i,j}=1)\\\end{cases}$
Haruku cannot wait for the matrix to change, so he asked you $Q$ questions. The $i$-th question is as follows.
- Is the value of $X_{T_i,R_i,C_i}$ $0$ or $1$?
Input
$N$ $A_1\ A_2\ \dots\ A_N$ $B_2$ $B_3$ $\vdots$ $B_N$ $Q$ $T_1\ R_1\ C_1$ $T_2\ R_2\ C_2$ $\vdots$ $T_Q\ R_Q\ C_Q$
- $1\leq N,Q\leq 2\times 10^5$
- $A_i,B_i\in \{0,1\}$
- $0\leq T_i\leq 10^{18}$
- $1\leq R_i,C_i\leq N$
- All input values are integers.
Output
Output $Q$ lines.
On the $i$-th line, output the answer to the $i$-th question.
Sample
Sample 1
Input
4 1 1 0 1 1 1 0 6 0 1 1 0 3 2 1 3 2 1 4 1 1 2 2 998244353 4 4
Output
1 0 1 0 0 1
- $X_{0,1,1}=A_1=1$.
- $X_{0,3,2}=0$.
- $X_{1,3,2}=\text{nand}(X_{0,2,2},X_{0,3,1})=\text{nand}(0,B_3)=\text{nand}(0,1)=1$.
- $X_{1,4,1}=X_{0,4,1}=B_4=0$.
- $X_{1,2,2}=\text{nand}(X_{0,1,2},X_{0,2,1})=\text{nand}(A_2,B_2)=\text{nand}(1,1)=0$.
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。