結果

問題 No.142 単なる配列の操作に関する実装問題
ユーザー koba-e964koba-e964
提出日時 2015-06-19 22:12:03
言語 C++11
(gcc 11.4.0)
結果
AC  
実行時間 1,545 ms / 5,000 ms
コード長 1,461 bytes
コンパイル時間 374 ms
コンパイル使用メモリ 57,644 KB
実行使用メモリ 7,272 KB
最終ジャッジ日時 2023-09-21 09:51:40
合計ジャッジ時間 6,816 ms
ジャッジサーバーID
(参考情報)
judge15 / judge13
このコードへのチャレンジ(β)

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 443 ms
7,260 KB
testcase_01 AC 1,258 ms
7,272 KB
testcase_02 AC 1,545 ms
7,256 KB
testcase_03 AC 408 ms
7,240 KB
testcase_04 AC 1,223 ms
7,196 KB
権限があれば一括ダウンロードができます

ソースコード

diff #

#include <iostream>
#include <sstream>

#define REP(i,s,n) for(int i=(int)(s);i<(int)(n);i++)

using namespace std;
typedef unsigned long long int ull;
const double EPS=1e-9;

const int N = 40000;

const int W = 64;
ull a[N];
ull room[10000];


int main(void){
  int n,s,x,y,z,q;
  cin >> n >> s >> x >> y >> z >> q;
  ull tmp = s;
  REP(i, 0, n) {
    a[i / W] |= (tmp % 2) << (i % W);
    tmp = tmp * x + y;
    tmp %= z;
  }
  REP(loop_var, 0, q) {
    int s,t,u,v;
    cin >> s >> t >> u >> v;
    s--, u--;
    ull s64 = s % 64;
    if (s / 64 == t / 64) {
      room[0] = a[s/64] >> s64;
      room[1] = 0;
    } else {
      room[0] = a[s/64] >> s64;
      REP(i, s / 64 + 1, t / 64 + 1) {
	room[i - s / 64 - 1] |= s64 ? (a[i] << (64 - s64)) : 0;
	room[i - s / 64] = a[i] >> s64;
      }
      room[t / 64 - s / 64 + 1] = 0;
    }
    ull u64 = u % 64;
    ull v64 = v % 64;
    if (u / 64 == v / 64) {
      a[u / 64] ^= (room[0] << u64) & ((1ULL << v64) - 1);
    } else {
      a[u / 64] ^= room[0] << u64;
      REP(i, u / 64 + 1, v / 64) {
	a[i] ^= room[i - u / 64] << u64;
	a[i] ^= u64 ? room[i - u / 64 - 1] >> (64 - u64) : 0;
      }
      ull sk = room[v / 64 - u / 64] << u64;
      sk ^= u64 ? room[v / 64 - u / 64 - 1] >> (64 - u64) : 0;      
      sk &= (1ULL << v64) - 1;
      a[v / 64] ^= sk;
    }
  }
  stringstream ss;
  REP(i, 0, n) {
    ss << (a[i / 64] & (1ULL << (i % 64)) ? 'O' : 'E');
  }
  cout << ss.str();
  cout << endl;
}
0