結果

問題 No.142 単なる配列の操作に関する実装問題
ユーザー OnjuOnju
提出日時 2015-02-03 01:06:32
言語 C++11
(gcc 11.4.0)
結果
WA  
実行時間 -
コード長 2,426 bytes
コンパイル時間 556 ms
コンパイル使用メモリ 74,392 KB
実行使用メモリ 11,556 KB
最終ジャッジ日時 2024-06-23 06:55:40
合計ジャッジ時間 4,364 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge3
このコードへのチャレンジ
（要ログイン）

テストケース

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

ソースコード

diff # 

//まだ途中、速度判定だけやっておきたい
//No.142 単なる配列の操作に関する実装問題

//メモ
//  繰り上げ・繰り下げのため配列前後に0詰め1byte用意
//  効率はよくない気がする
#include <iostream>
#include <memory>
#include <cstring>
#include <climits>
#include <cmath>
#include <bitset>
#include <vector>
#include <iterator>
#include <algorithm> 

#define pl(x) cout << (x) << endl
#define pbit64(x) cout << (*new bitset<64>(x)).to_string() << endl
#define pbit(x) cout << (*new bitset<32>(x)).to_string() << endl

typedef long long LL;

using namespace std;

//#define BIT_LEN 32
int BIT_LEN = sizeof(int) * 8;

int getF(int* b, int bp, int fp)
{
	int fri = fp / BIT_LEN + 1;
	bp %= BIT_LEN;
	fp %= BIT_LEN;

	if (bp <= fp)
		return ((int)((LL)b[fri] + (b[fri + 1] << BIT_LEN)) >> (fp - bp));
	else
		return ((int)((((LL)b[fri] << BIT_LEN) + b[fri - 1]) >> (BIT_LEN - bp + fp)));
}

//R側フィルタ取得
int filR(int* b, int br, int fr)
{
	return getF(b, br, fr) & (UINT_MAX << br);
}

//L側フィルタ取得
int filL(int* b, int bl, int fl)
{
	return getF(b, bl, fl) & (UINT_MAX >> (BIT_LEN - bl - 1));
}

//選択範囲のXOR
void bxor(int* b, int br, int fr, int fl)
{
	int bl = br - fr + fl;
	int fli = fl / BIT_LEN + 1;
	int fri = fr / BIT_LEN + 1;
	int bri = br / BIT_LEN + 1;
	int bli = bri + fli - fri;
	int dif = fli - bli;

	if (bri == bli)
	{
		b[bri] ^= filR(b, br, fr) & filL(b, bl, fl);
	}
	else
	{
		//R->L
		if (br <= fr)
		{
			b[bri] ^= filR(b, br, fr);
			for (int i = bri + 1; i < bli; ++i)
				b[i] ^= b[i + dif];
			b[bli] ^= filL(b, bl, fl);
		}
		//L->R
		else
		{
			b[bli] ^= filL(b, bl, fl);
			for (int i = bli - 1; i > bri; --i)
				b[i] ^= b[i + dif];
			b[bri] ^= filR(b, br, fr);
		}
	}
}

int main()
{
	int N, S, X, Y, Z, Q, T, U, V;
	cin >> N >> S >> X >> Y >> Z >> Q;
	int bsize = (N + BIT_LEN - 1) / BIT_LEN + 2;	//前後1byteは0詰め固定
	int* A = new int[N];
	int* B = new int[bsize];
	A[0] = S;
	memset(B, 0, sizeof(int)*(bsize));

	for (int i = 1; i < N; ++i)
		A[i] = (X*A[i - 1] + Y) % Z;

	//bit化
	for (int i = 0; i < N; ++i)
		B[i / BIT_LEN + 1] += (A[i] & 1) << (i % BIT_LEN);

	for (int i = 0; i < Q; ++i)
	{
		cin >> S >> T >> U >> V;
		bxor(B, U - 1, S - 1, T - 1);
	}

	for (int i = 0; i < N; ++i)
	{
		if (B[i / BIT_LEN + 1] & (1 << (i%BIT_LEN)))
			cout << 'O';
		else
			cout << 'E';
	}

	return 0;
}
0