結果

問題 No.142 単なる配列の操作に関する実装問題
ユーザー 👑 hos.lyrichos.lyric
提出日時 2015-02-02 00:57:33
言語 C++11
(gcc 11.4.0)
結果
AC  
実行時間 1,292 ms / 5,000 ms
コード長 2,350 bytes
コンパイル時間 630 ms
コンパイル使用メモリ 87,092 KB
実行使用メモリ 5,736 KB
最終ジャッジ日時 2023-09-05 10:31:09
合計ジャッジ時間 5,919 ms
ジャッジサーバーID
（参考情報） 		judge12 / judge14
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 266 ms
5,612 KB
testcase_01 AC 1,027 ms
5,736 KB
testcase_02 AC 1,292 ms
5,676 KB
testcase_03 AC 255 ms
5,628 KB
testcase_04 AC 1,013 ms
5,596 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <cassert>
#include <iostream>
#include <sstream>
#include <string>
#include <vector>
#include <queue>
#include <deque>
#include <set>
#include <map>
#include <utility>
#include <numeric>
#include <algorithm>
#include <bitset>
#include <complex>
#include <cstdint>
#include <unordered_set>
#include <unordered_map>

using namespace std;

typedef long long Int;
typedef vector<int> vint;
typedef pair<int, int> pint;
#define mp make_pair

template <typename T1, typename T2> ostream &operator<<(ostream &os, const pair<T1, T2> &a) { return os << "(" << a.first << ", " << a.second << ")"; };
template <typename T> void pv(T a, T b) { for (T i = a; i != b; ++i) cout << *i << " "; cout << endl; }
template <typename T> void chmin(T &t, const T &f) { if (t > f) t = f; }
template <typename T> void chmax(T &t, const T &f) { if (t < f) t = f; }
int in() { int x; scanf("%d", &x); return x; }


int N;
Int S, X, Y, Z;
int Q;

char ans[2000010];

uint64_t MASKS[110];
uint64_t a[100010];
uint64_t b[100010];

void generate() {
	Int s = S;
	for (int i = 0; i < N; ++i) {
		if (s & 1) {
			a[i >> 6] ^= 1ULL << (i & 63);
		}
		s = (X * s + Y) % Z;
	}
}

int main() {
	MASKS[0] = 0;
	for (int d = 1; d <= 64; ++d) {
		MASKS[d] = MASKS[d - 1] << 1 | 1;
	}
	
	for (; ~scanf("%d%lld%lld%lld%lld", &N, &S, &X, &Y, &Z); ) {
#ifdef LOCAL
		memset(a, 0, sizeof(a));
#endif
		generate();
		for (Q = in(); Q--; ) {
/*
for (int i = 0; i < N; ++i) {
ans[i] = "EO"[(a[i >> 6] >> (i & 63)) & 1];
}
ans[N] = '\0';
puts(ans);
//*/
			const int s = in() - 1;
			const int t = in();
			const int u = in() - 1;
			const int v = in();
			assert(t - s == v - u);
			const int l = (t - s) >> 6;
assert(l>=0);
			{
				const int r = s & 63;
				const int rr = 64 - r;
				int p = s >> 6;
				for (int j = 0; j <= l; ++j) {
					b[j] = a[p++] >> r;
					if (r) {
						b[j] |= a[p] << rr;
					}
				}
				b[l] &= MASKS[(t - s) & 63];
			}
// cout<<"b : ";pv(b,b+l+1);
			{
				const int r = u & 63;
				const int rr = 64 - r;
				int p = u >> 6;
				for (int j = 0; j <= l; ++j) {
					a[p++] ^= b[j] << r;
					if (r) {
						a[p] ^= b[j] >> rr;
					}
				}
			}
		}
		for (int i = 0; i < N; ++i) {
			ans[i] = "EO"[(a[i >> 6] >> (i & 63)) & 1];
		}
		ans[N] = '\0';
		puts(ans);
	}
	
	return 0;
}
0