結果

問題 No.142 単なる配列の操作に関する実装問題
ユーザー koyumeishikoyumeishi
提出日時 2015-02-02 01:45:22
言語 C++11
(gcc 11.4.0)
結果
AC  
実行時間 1,640 ms / 5,000 ms
コード長 2,502 bytes
コンパイル時間 912 ms
コンパイル使用メモリ 85,100 KB
実行使用メモリ 19,188 KB
最終ジャッジ日時 2023-09-05 10:35:13
合計ジャッジ時間 7,212 ms
ジャッジサーバーID
（参考情報） 		judge12 / judge15
このコードへのチャレンジ（β）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 357 ms
19,016 KB
testcase_01 AC 1,307 ms
18,972 KB
testcase_02 AC 1,640 ms
19,188 KB
testcase_03 AC 344 ms
18,896 KB
testcase_04 AC 1,279 ms
18,964 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <iostream>
#include <vector>
#include <cstdio>
#include <sstream>
#include <map>
#include <string>
#include <algorithm>
#include <queue>
#include <cmath>
#include <set>
#include <bitset>

using namespace std;

#define SZ 1200

//#define DBG_

void init(vector<bitset<SZ>> &v, int n, int s, long long x, long long y, long long z){
	vector<long long> a(n, 1);
	a[0] = s;
	v[0/SZ].set(0%SZ, a[0]&1);

	for(int i=1; i<n; i++){
		a[i] = (x*a[i-1] + y) % z;
		v[i/SZ].set(i%SZ, a[i]&1);
	}

#ifdef DBG_
	for(int i=0; i<n; i++){
		cerr << a[i] << " " ;
	}
	cerr << endl;
#endif

}

void dbg(bitset<SZ> x){
	string s = x.to_string<char,std::string::traits_type,std::string::allocator_type>();
	cerr << s << endl;
}

int main(){
	int n,s,x,y,z;
	cin >> n >> s >> x >> y >> z;



	int k = n/SZ + 1;
	vector<bitset<SZ>> vec(k);

	init(vec,n,s,x,y,z);

#ifdef DBG_
	for(int i=0; i<k; i++){
		dbg(vec[i]);
	}
#endif

	int q;
	cin >> q;
	while(q-->0){
		int s_, t, u, v;
		scanf("%d %d %d %d", &s_, &t, &u, &v);
		s_--;
		t--;
		u--;
		v--;

		vector<bitset<SZ>> tmp(vec.begin() + s_/SZ , vec.begin() + (t+1)/SZ + 1);

#ifdef DBG_
		cerr << "tmp " << endl;
		for(int i=0; i<tmp.size(); i++){
			dbg(tmp[i]);
		}
#endif

		tmp[0] >>= s_%SZ;
		tmp[0] <<= s_%SZ;

#ifdef DBG_
		cerr << "tmp s " << endl;
		for(int i=0; i<tmp.size(); i++){
			dbg(tmp[i]);
		}
#endif

		tmp[tmp.size()-1] <<= SZ-((t+1)%SZ);
		tmp[tmp.size()-1] >>= SZ-((t+1)%SZ);

#ifdef DBG_
		cerr << "tmp t " << endl;
		for(int i=0; i<tmp.size(); i++){
			dbg(tmp[i]);
		}
#endif

		int d = (u%SZ) - (s_%SZ);

		for(int i=0; i<tmp.size(); i++){

			#ifdef DBG_
			cerr << "rewrite from :" << endl;
			dbg(vec[u/SZ+i]);
			#endif
			if(d==0){
				vec[u/SZ + i] ^= tmp[i];
			}
			if(d<0){


				vec[u/SZ + i] ^= (tmp[i] >> abs(d));
				if(i+1<tmp.size()){
					vec[u/SZ + i] ^= ( tmp[i+1] << (SZ - abs(d)) );
				}


			}else if(d>0){

				vec[u/SZ + i] ^= (tmp[i] << abs(d));
				if(i>0){
					vec[u/SZ + i] ^= ( tmp[i-1] >> (SZ - abs(d)) );
				}
			}

			#ifdef DBG_
			cerr << "to :" << endl;
			dbg(vec[u/SZ+i]);
			cerr << endl;
			#endif

		}
		if(d>0 && u/SZ + tmp.size() < vec.size() ){
			vec[u/SZ + tmp.size()] ^= ( tmp[tmp.size()-1] >> (SZ - abs(d)) );
		}

#ifdef DBG_
		cerr << "res " << endl;
		for(int i=0; i<k; i++){
			dbg(vec[i]);
		}
#endif

	}

#ifdef DBG_
	for(int i=0; i<k; i++){
		dbg(vec[i]);
	}
#endif

	string ss;
	for(int i=0; i<n; i++){
		ss.push_back(vec[i/SZ][i%SZ]?'O':'E');
	}
	cout << ss << endl;
	return 0;
}
0