No.142 An Implementation Problem About Simple Array Operations
タグ : / 解いたユーザー数 41
作問者 :
LayCurse
Problem Statement
Warning: The intended solution runs in about $1$ second ($967$ms) in C++. Depending on the language, the same approach as the intended solution may result in TLE.
(The code of the intended solution is meant to be straightforward code, and is not meant to be heavily optimized.)
Perform the operations below and find the final array $A = A_1,A_2,\ldots,A_N$.
However, since the elements of the array $A$ may become large, output only whether each element is even or odd.
Here, a contiguous subarray of the array $A$ is denoted by $A[i,j] = A_i,A_{i+1},\ldots,A_j$.
For example, when we write $B = A[i,i+10]$, we have $B_3 = A_{i+2}$.
First, the number of elements $N$ of the array $A$, a random seed $S$, and random generation parameters $X, Y, Z$ are given. Create the array $A$ by the following method:
$\qquad A_1 = S$,
$\qquad A_{k+1} = (X \times A_k + Y)\ {\rm mod}\ Z, \;\; k=1,2,\ldots,N-1$.
Next, $Q$ operations are given.
Each operation is a tuple of $4$ positive integers $S,T,U,V$, and does the following.
Copy the elements from the $S$-th through the $T$-th of the array $A$, and let $B = A[S,T]$.
Then, add each element of $B$ to the corresponding element of $A[U,V]$. That is, perform the assignment
$\qquad A_k \leftarrow A_k + B_{k-U+1}, \;\; U \leq k \leq V$
.
Write a program that, after all $Q$ operations are finished, outputs the string of length $N$ obtained by replacing each element of the array $A$ with $\verb|E|$ if it is even and with $\verb|O|$ if it is odd.
Input
$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$ denote the values of $S,T,U,V$ in the $k$-th operation.
$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$
Output
Output the answer string.
Note that the character for odd is not the digit zero but the letter O (because it stands for "odd"!).
Sample
Sample 1
Input
10 8 1 3 5 3 3 5 7 9 3 10 1 8 1 3 1 3
Output
EEEOOOOEEE
Generating the sequence with the random numbers first gives
$\qquad A = 8,1,4,2,0,3,1,4,2,0$
and after the $1$st operation it becomes
$\qquad A = 8,1,4,2,0,3,5,6,2,0$
and after the $2$nd operation it becomes
$\qquad A = 12,3,4,5,5,9,7,6,2,0$
and after the $3$rd operation it becomes
$\qquad A = 24,6,8,5,5,9,7,6,2,0$
.
The answer is a palindrome. Yay!
Sample 2
Input
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
Output
OEEEOOOEOOOOEOOOEEEO
Generating the sequence with the random numbers first gives
$\qquad A = 8,1,11,13,2,15,10,9,5,8,1,11,13,2,15,10,9,5,8,1$
and after that, it changes with each operation as follows:
After the $1$st operation: $8,1,11,13,2,23,11,20,18,10,16,21,22,7,23,11,20,18,8,1$
After the $2$nd operation: $8,1,11,35,9,46,22,40,36,18,17,21,22,7,23,11,20,18,8,1$
After the $3$rd operation: $8,9,12,46,44,55,68,62,76,54,35,21,22,7,23,11,20,18,8,1$
After the $4$th operation: $43,30,34,53,67,66,88,80,84,55,35,21,22,7,23,11,20,18,8,1$
After the $5$th operation: $43,30,34,96,97,100,88,80,84,55,35,21,22,7,23,11,20,18,8,1$
After the $6$th operation: $43,30,34,96,97,143,118,80,84,55,35,21,22,7,23,11,20,18,8,1$
After the $7$th operation: $43,30,34,96,97,143,139,102,91,55,35,21,22,7,23,11,20,18,8,1$
.
The answer is a palindrome again. Nice!
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。