問題一覧 > 通常問題

No.142 単なる配列の操作に関する実装問題

レベル : / 実行時間制限 : 1ケース 5.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 35
作問者 : LayCurseLayCurse
2 ProblemId : 206 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2015-11-14 17:47:12

問題文

Warning: 想定解法はC++で実行時間 $1$ 秒程度($967$ms)です.言語によっては想定解法と同じ方法ではTLEになる可能性があります.
(想定解法のコードは素直なコードのつもりで,ごりごりに最適化をしているわけではないつもりです)

次の操作を行った後,最終的な配列 $A = A_1,A_2,\ldots,A_N$ を求めてください.
ただし,配列 $A$ の各要素は大きくなる可能性があるため,各要素が偶数か奇数かのみを出力してください.
ここで,配列 $A$ の連続する部分列を $A[i,j] = A_i,A_{i+1},\ldots,A_j$ と書き表します.
例えば,$B = A[i,i+10]$ と書いた時,$B_3 = A_{i+2}$ です.

最初に,配列 $A$ の要素の数 $N$,乱数の種 $S$ と,乱数生成のパラメータ $X, Y, Z$ が与えられるので,次の方法で配列 $A$ を作成します:
$\qquad A_1 = S$,
$\qquad A_{k+1} = (X \times A_k + Y)\ {\rm mod}\ Z, \;\; k=1,2,\ldots,N-1$.

次に $Q$ 個の処理が与えられます.
各処理は,$4$ つの正整数 $S,T,U,V$ の組で,次のような操作を行います.
配列 $A$ の $S$ 番目の要素から,$T$ 番目の要素までをコピーし,$B = A[S,T]$ とします.
そして,$A[U,V]$ の各要素に $B$ の各要素を足し込みます.つまり,
$\qquad A_k \leftarrow A_k + B_{k-U+1}, \;\; U \leq k \leq V$
と代入操作を行います.

この $Q$ 個の操作が全て終わった後,配列 $A$ の各要素に対して,偶数であれば $\verb|E|$,奇数であれば $\verb|O|$ と置き換えてできる長さ $N$ の文字列を出力するプログラムを書いてください.

入力

$N$ $S$ $X$ $Y$ $Z$
$Q$
$S_1$ $T_1$ $U_1$ $V_1$
$S_2$ $T_2$ $U_2$ $V_2$
$\vdots$
$S_Q$ $T_Q$ $U_Q$ $V_Q$

$S_k,T_k,U_k,V_k$ は $k$ 個目の操作における $S,T,U,V$ の値を意味する
$1 \leq N \leq 2000000 = 2 \times 10^6$
$0 \leq S,X,Y \leq 1000000000 = 10^9$
$1 \leq Z \leq 1000000000 = 10^9$
$0 \leq Q \leq 200000 = 2 \times 10^5$
$1 \leq S_k \leq T_k \leq N$
$1 \leq U_k \leq V_k \leq N$
$T_k - S_k = V_k - U_k \leq 10^5$

出力

答えの文字列を出力してください.
なお,奇数に対応する文字はゼロではなくアルファベットのオー(oddですから!)です.

サンプル

サンプル1
入力
10 8 1 3 5
3
3 5 7 9
3 10 1 8
1 3 1 3
出力
EEEOOOOEEE

最初に乱数で数列を作ると,
$\qquad A = 8,1,4,2,0,3,1,4,2,0$
となり,$1$ 回目の操作の後には,
$\qquad A = 8,1,4,2,0,3,5,6,2,0$
となり,$2$ 回目の操作の後には,
$\qquad A = 12,3,4,5,5,9,7,6,2,0$
となり,$3$ 回目の操作の後には,
$\qquad A = 24,6,8,5,5,9,7,6,2,0$
となる.
答えは回文だね.やったぁ.

サンプル2
入力
20 8 4 7 19
7
1 13 6 18
13 20 4 11
1 10 2 11
11 20 1 10
1 3 4 6
1 2 6 7
12 14 7 9
出力
OEEEOOOEOOOOEOOOEEEO

最初に乱数で数列を作ると,
$\qquad A = 8,1,11,13,2,15,10,9,5,8,1,11,13,2,15,10,9,5,8,1$
となり,その後は各操作の後に,
$1$ 回目の操作の後:$8,1,11,13,2,23,11,20,18,10,16,21,22,7,23,11,20,18,8,1$
$2$ 回目の操作の後:$8,1,11,35,9,46,22,40,36,18,17,21,22,7,23,11,20,18,8,1$
$3$ 回目の操作の後:$8,9,12,46,44,55,68,62,76,54,35,21,22,7,23,11,20,18,8,1$
$4$ 回目の操作の後:$43,30,34,53,67,66,88,80,84,55,35,21,22,7,23,11,20,18,8,1$
$5$ 回目の操作の後:$43,30,34,96,97,100,88,80,84,55,35,21,22,7,23,11,20,18,8,1$
$6$ 回目の操作の後:$43,30,34,96,97,143,118,80,84,55,35,21,22,7,23,11,20,18,8,1$
$7$ 回目の操作の後:$43,30,34,96,97,143,139,102,91,55,35,21,22,7,23,11,20,18,8,1$
と変化していく.
答えはやっぱり回文だね.やったね.

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