結果

問題 No.142 単なる配列の操作に関する実装問題
ユーザー やまぞうやまぞう
提出日時 2015-04-12 23:55:48
言語 C++11
(gcc 11.4.0)
結果
WA  
実行時間 -
コード長 2,965 bytes
コンパイル時間 445 ms
コンパイル使用メモリ 62,296 KB
実行使用メモリ 5,376 KB
最終ジャッジ日時 2024-07-04 14:05:45
合計ジャッジ時間 5,833 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge5
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 WA -
testcase_01 AC 960 ms
5,376 KB
testcase_02 AC 1,157 ms
5,376 KB
testcase_03 AC 379 ms
5,376 KB
testcase_04 AC 912 ms
5,376 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <iostream>
#include <vector>
#include <climits>
#include <fstream>

using namespace std;


typedef unsigned int UINT;
typedef unsigned long long ULONGLONG;
typedef unsigned long WORD;
#define WORD_BITS (CHAR_BIT * sizeof(WORD))
#define INDEX(x) ((x) / (WORD_BITS))
#define OFFSET(x) ((x) % (WORD_BITS))
#define UPDIV(x, n) (((x) + (n) - 1) / (n))

#define MAX_N 2000000
WORD ARR[UPDIV(MAX_N, WORD_BITS) + 2];
#define DATA(n) ARR[(n) + 1]

int main()
{
#if 0
	ifstream in("test_in/in1");
	ofstream out("temp_1.txt");
#else
#define in cin
#define out cout
#endif

	UINT N, S, X, Y, Z;
	in >> N >> S >> X >> Y >> Z;

	ULONGLONG a = S;
	for (UINT i = 0; i < N; i++) {
		DATA(INDEX(i)) |= (a & 1) << OFFSET(i);
		a = (X * a + Y) % Z;
	}
	UINT Q;
	in >> Q;
	for (UINT q = 0; q < Q; q++) {
		UINT s, t, u, v;
		in >> s >> t >> u >> v;
		s--;
		t--;
		u--;
		v--;

		WORD w;
		if (s >= u) {
			if (INDEX(s) == INDEX(t)) {
				w = DATA(INDEX(s));
				w &= (WORD(~0U)) >> (WORD_BITS - OFFSET(t) - 1);
				w >>= OFFSET(s);
				DATA(INDEX(u)) ^= w << OFFSET(u);
				if (OFFSET(u) != 0) DATA(INDEX(u) + 1) ^= w >> (WORD_BITS - OFFSET(u));
			}
			else {
				if (OFFSET(s) != 0) {
					w = DATA(INDEX(s));
					w >>= OFFSET(s);
					DATA(INDEX(u)) ^= w << OFFSET(u);
					if (OFFSET(u) != 0) DATA(INDEX(u) + 1) ^= w >> (WORD_BITS - OFFSET(u));
					u += WORD_BITS - OFFSET(s);
					s += WORD_BITS - OFFSET(s);
				}
				while (INDEX(s) < INDEX(t)) {
					w = DATA(INDEX(s));
					DATA(INDEX(u)) ^= w << OFFSET(u);
					if (OFFSET(u) != 0) DATA(INDEX(u) + 1) ^= w >> (WORD_BITS - OFFSET(u));
					u += WORD_BITS;
					s += WORD_BITS;
				}
				w = DATA(INDEX(s));
				w &= (WORD(~0)) >> (WORD_BITS - OFFSET(t) - 1);
				DATA(INDEX(u)) ^= w << OFFSET(u);
				if (OFFSET(u) != 0) DATA(INDEX(u) + 1) ^= w >> (WORD_BITS - OFFSET(u));
			}
		}
		else {
			if (INDEX(t) == INDEX(s)) {
				w = DATA(INDEX(t));
				w &= WORD(~0) << OFFSET(s);
				w <<= (WORD_BITS - OFFSET(t) - 1);
				DATA(INDEX(v)) ^= w >> (WORD_BITS - OFFSET(v) - 1);
				if (OFFSET(v) != WORD_BITS - 1) DATA(INDEX(v) - 1) ^= w << (OFFSET(v) + 1);
			}
			else {
				if (OFFSET(t) != WORD_BITS - 1) {
					w = DATA(INDEX(t));
					w <<= (WORD_BITS - OFFSET(t) - 1);
					DATA(INDEX(v)) ^= w >> (WORD_BITS - OFFSET(v) - 1);
					if (OFFSET(v) != WORD_BITS - 1) DATA(INDEX(v) - 1) ^= w << (OFFSET(v) + 1);
					v -= OFFSET(t) + 1;
					t -= OFFSET(t) + 1;
				}
				while (INDEX(t) > INDEX(s)) {
					w = DATA(INDEX(t));
					DATA(INDEX(v)) ^= w >> (WORD_BITS - OFFSET(v) - 1);
					if (OFFSET(v) != WORD_BITS - 1) DATA(INDEX(v) - 1) ^= w << (OFFSET(v) + 1);
					v -= WORD_BITS;
					t -= WORD_BITS;
				}
				w = DATA(INDEX(t));
				w &= WORD(~0) << OFFSET(s);
				DATA(INDEX(v)) ^= w >> (WORD_BITS - OFFSET(v) - 1);
				if (OFFSET(v) != WORD_BITS - 1) DATA(INDEX(v) - 1) ^= w << (OFFSET(v) + 1);
			}
		}
	}
	for (UINT i = 0; i < N; i++) {
		out << "EO"[(DATA(INDEX(i)) >> OFFSET(i)) & 1];
	}
	out << endl;
}
0