結果

問題 No.142 単なる配列の操作に関する実装問題
ユーザー やまぞうやまぞう
提出日時 2015-04-12 01:05:31
言語 C++11
(gcc 11.4.0)
結果
WA  
実行時間 -
コード長 1,711 bytes
コンパイル時間 566 ms
コンパイル使用メモリ 65,412 KB
実行使用メモリ 6,948 KB
最終ジャッジ日時 2024-07-04 13:53:58
合計ジャッジ時間 10,354 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge1
このコードへのチャレンジ
（要ログイン）

テストケース

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

ソースコード

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 UPDIV(x, n) (((x) + (n) - 1) / (n))
#define INDEX(x) ((x) / WORD_BITS)
#define OFFSET(x) ((x) % WORD_BITS)

//#define MAX_N 2000000
//char result[MAX_N + 1];
//WORD A[UPDIV(MAX_N, WORD_BITS) + 1];
//WORD B[UPDIV(MAX_N, WORD_BITS) + 1];

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

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

	vector<UINT> A, B;
	A.resize(UPDIV(N, WORD_BITS) + 1);
	B.resize(UPDIV(N, WORD_BITS) + 1);

	ULONGLONG a = S;
	for (UINT i = 0; i < N; i++) {
		A[i / WORD_BITS] |= (a & 1) << (i % WORD_BITS);
		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--;

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