結果

問題 No.142 単なる配列の操作に関する実装問題
ユーザー Yang33
提出日時 2018-05-03 18:02:06
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 1,896 ms / 5,000 ms
コード長 3,457 bytes
コンパイル時間 1,693 ms
コンパイル使用メモリ 172,744 KB
実行使用メモリ 19,416 KB
最終ジャッジ日時 2024-06-28 00:47:02
合計ジャッジ時間 8,730 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 5
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

#include <bits/stdc++.h>
using namespace std;
#define ALL(a)  begin((a)),end((a))
#define RALL(a) (a).rbegin(), (a).rend()
#define SZ(a) int((a).size())
#define SORT(c) sort(ALL((c)))
#define RSORT(c) sort(RALL((c)))
#define UNIQ(c) (c).erase(unique(ALL((c))), end((c)))
#define FOR(i, s, e) for (int(i) = (s); (i) < (e); (i)++)
#define FORR(i, s, e) for (int(i) = (s); (i) > (e); (i)--)
#define debug(x) cerr << #x << ": " << x << endl
/* -----  2018/05/03  Problem: yukicoder 142  / Link: http://yukicoder.me/problems/no/142  ----- */
/* ------問題------
次の操作を行った後，最終的な配列 A=A1,A2,…,AN を求めてください．
ただし，配列 A の各要素は大きくなる可能性があるため，各要素が偶数か奇数かのみを出力してください．
ここで，配列 A の連続する部分列を A[i,j]=Ai,Ai+1,…,Aj と書き表します．
例えば，B=A[i,i+10] と書いた時，B3=Ai+2 です．
最初に，配列 A の要素の数 N，乱数の種 S と，乱数生成のパラメータ X,Y,Z が与えられるので，次の方法で配列 A を作成します：
A1=S，
Ak+1=(X×Ak+Y) mod Z,k=1,2,…,N−1．
次に Q 個の処理が与えられます．
各処理は，4 つの正整数 S,T,U,V の組で，次のような操作を行います．
配列 A の S 番目の要素から，T 番目の要素までをコピーし，B=A[S,T] とします．
そして，A[U,V] の各要素に B の各要素を足し込みます．つまり，
Ak←Ak+Bk−U+1,U≤k≤V
と代入操作を行います．
この Q 個の操作が全て終わった後，配列 A の各要素に対して，偶数であれば E，奇数であれば O と置き換えてできる長さ N 
    の文字列を出力するプログラムを書いてください．
-----問題ここまで----- */
/* -----解説等-----
厳しい
----解説ここまで---- */
int main() {
    cin.tie(0);
    ios_base::sync_with_stdio(false);
    using VL = vector<unsigned long long >;
    using LL = unsigned long long;
    long long N, S, X, Y, Z;
    cin >> N >> S >> X >> Y >> Z;
    vector<long long> a(N);
    a[0] = S;
    FOR(i, 1, N) {
        a[i] = (X*a[i - 1] + Y) % Z;
    }
    const int W = 64;
    VL bit((N + W - 1) / W + 1, 0);
    FOR(i, 0, N) {
        if (a[i] % 2)bit[i / W] |= (1LL << (i%W));
    }
    int Q; cin >> Q;
    VL tmp((N + W - 1) / W, 0);
    FOR(q, 0, Q) {
        int s, t, u, v; cin >> s >> t >> u >> v;
        s--, u--;
        // [s,t)を先頭にもってきて[u,v)に加算
        int len = t - s;
        {
            int i = 0, j = s;
            if (j%W == 0) {
                for (; i + W <= len; i += W, j += W) {
                    tmp[i / W] = bit[j / W];
                }
            }
            else {
                int ss = j%W, tt = W - ss;
                LL cur = bit[j / W], nx;
                for (; i + W <= len; i += W, j += W) {
                    nx = bit[j / W + 1];
                    tmp[i / W] = (cur >> ss) | (nx << tt);
                    cur = nx;
                }
            }
            tmp[i / W] = 0;
            for (; i < len; i++, j++) {
                tmp[i / W] |= (bit[j / W] >> (j%W) & 1) << (i%W);
            }
        }
        {
            int i = 0, j = u;
            if (j % W == 0) {
                for (; i + W <= len; i += W, j += W) {
                    bit[j / W] ^= tmp[i / W];
                }
            }
            else {
                int ss = j % W, tt = W - ss;
                LL p;
                for (; i + W <= len; i += W, j += W) {
                    p = tmp[i / W];
                    bit[j / W] ^= p << ss;
                    bit[j / W + 1] ^= p >> tt;
                }
            }
            for (; i < len; ++i, ++j)
                bit[j / W] ^= (tmp[i / W] >> (i % W) & 1) << (j % W);
        }
    }
    FOR(i, 0, N) {
        bool x = bit[i / W] & (1LL << (i%W));
        cout << "EO"[x];
    }cout << endl;
    return 0;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0