結果
問題 | 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 longtypedef 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;}}