/ 
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 800 点
問題文
N \times N の行列を考えます。この行列の i 行目、j 列目の値を a_{i, j} とします。i = 1 か j = 1 を満たす a_{i, j} については 0, 1, 2 のいずれかの値が入力で与えられます。残りの値は以下の規則に従い定めます。
- a_{i,j} = \mathrm{mex}(a_{i-1,j}, a_{i,j-1}) (2 \leq i, j \leq N)。ただし \mathrm{mex}(x, y) は次の表に従う。
| \mathrm{mex}(x, y) | y=0 | y=1 | y=2 |
|---|---|---|---|
| x=0 | 1 | 2 | 1 |
| x=1 | 2 | 0 | 0 |
| x=2 | 1 | 0 | 0 |
行列の要素のうち、値が 0, 1, 2 であるものはそれぞれ何個でしょうか？
制約
- 1 \leq N \leq 500{,}000
- 入力される a_{i, j} の値はすべて 0, 1, 2 のいずれか
入力
入力は以下の形式で標準入力から与えられる．
N
a_{1, 1} a_{1, 1} ... a_{1, N}
a_{2, 1}
:
a_{N, 1}
出力
0 の個数、1 の個数、2 の個数を空白区切りで出力せよ。
入力例 1
4 1 2 0 2 0 0 0
出力例 1
7 4 5
行列は以下のようになります。
1 2 0 2 0 1 2 0 0 2 0 1 0 1 2 0
Score : 800 points
Problem Statement
Consider an N \times N matrix. Let us denote by a_{i, j} the entry in the i-th row and j-th column. For a_{i, j} where i=1 or j=1 holds, its value is one of 0, 1 and 2 and given in the input. The remaining entries are defined as follows:
- a_{i,j} = \mathrm{mex}(a_{i-1,j}, a_{i,j-1}) (2 \leq i, j \leq N) where \mathrm{mex}(x, y) is defined by the following table:
| \mathrm{mex}(x, y) | y=0 | y=1 | y=2 |
|---|---|---|---|
| x=0 | 1 | 2 | 1 |
| x=1 | 2 | 0 | 0 |
| x=2 | 1 | 0 | 0 |
How many entries of the matrix are 0, 1, and 2, respectively?
Constraints
- 1 \leq N \leq 500{,}000
- a_{i,j}'s given in input are one of 0, 1 and 2.
Input
Input is given from Standard Input in the following format:
N
a_{1, 1} a_{1, 1} ... a_{1, N}
a_{2, 1}
:
a_{N, 1}
Output
Print the number of 0's, 1's, and 2's separated by whitespaces.
Sample Input 1
4 1 2 0 2 0 0 0
Sample Output 1
7 4 5
The matrix is as follows:
1 2 0 2 0 1 2 0 0 2 0 1 0 1 2 0