結果
問題 | No.5002 stick xor |
ユーザー |
![]() |
提出日時 | 2018-05-27 00:46:57 |
言語 | C++11(廃止可能性あり) (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 977 ms / 1,000 ms |
コード長 | 3,172 bytes |
コンパイル時間 | 34,605 ms |
実行使用メモリ | 1,548 KB |
スコア | -39,789 |
最終ジャッジ日時 | 2018-05-27 00:47:33 |
ジャッジサーバーID (参考情報) |
judge8 / |
純コード判定しない問題か言語 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 32 |
ソースコード
#include <bits/stdc++.h> using namespace std; #define int long long typedef pair<int, int> P; int dx[8] = {1, 0, -1, 0, 1, -1, -1, 1}; int dy[8] = {0, 1, 0, -1, 1, 1, -1, -1}; /* ifstream ifs("in.txt"); ofstream ofs("out.txt"); #define cin ifs #define cout ofs //*/ // xorshiftを用いた乱数 long long xor64(long long range) { static unsigned long long x = 88172645463325252ULL; x ^= x << 13; x ^= x >> 7; return (x ^= x << 17) % range; } // タイマー struct Timer { unsigned long long begin_cycle; double cycle_per_sec = 2.8e9; unsigned long long getCycle() { unsigned low, high; __asm__ volatile("rdtsc" : "=a"(low), "=d"(high)); return ((unsigned long long)low) | ((unsigned long long)high << 32); } double getTime() { return (getCycle() - begin_cycle) / cycle_per_sec; } void init() { begin_cycle = getCycle(); } }; int N, K; int L[550]; bool A[66][66]; int a[550], b[550], c[550], d[550]; double T = 0.9; Timer timer; signed main() { cin >> N >> K; for (int i = 0; i < K; i++) { cin >> L[i]; } for (int i = 0; i < N; i++) { string s; cin >> s; for (int j = 0; j < N; j++) { A[i][j] = s[j] == '1'; } } timer.init(); for (int i = 0; i < K; i++) { if (xor64(2) == 0) { a[i] = xor64(N); b[i] = xor64(N - L[i] + 1); c[i] = a[i]; d[i] = b[i] + L[i] - 1; } else { a[i] = xor64(N - L[i] + 1); b[i] = xor64(N); c[i] = a[i] + L[i] - 1; d[i] = b[i]; } for (int j = a[i]; j <= c[i]; j++) { for (int k = b[i]; k <= d[i]; k++) { A[j][k] ^= 1; } } } while (timer.getTime() < T) { int i = xor64(K); int diff = 0; for (int j = a[i]; j <= c[i]; j++) { for (int k = b[i]; k <= d[i]; k++) { A[j][k] ^= 1; diff += A[j][k] * 2 - 1; } } int na, nb, nc, nd; if (xor64(2) == 0) { na = xor64(N); nb = xor64(N - L[i] + 1); nc = na; nd = nb + L[i] - 1; } else { na = xor64(N - L[i] + 1); nb = xor64(N); nc = na + L[i] - 1; nd = nb; } for (int j = na; j <= nc; j++) { for (int k = nb; k <= nd; k++) { A[j][k] ^= 1; diff += A[j][k] * 2 - 1; } } if (diff < 0) { for (int j = a[i]; j <= c[i]; j++) { for (int k = b[i]; k <= d[i]; k++) { A[j][k] ^= 1; } } for (int j = na; j <= nc; j++) { for (int k = nb; k <= nd; k++) { A[j][k] ^= 1; } } } else { a[i] = na, b[i] = nb, c[i] = nc, d[i] = nd; } } for (int i = 0; i < K; i++) { cout << a[i] + 1 << " " << b[i] + 1 << " " << c[i] + 1 << " " << d[i] + 1 << endl; } }