結果
問題 | No.5002 stick xor |
ユーザー |
![]() |
提出日時 | 2018-05-26 15:55:44 |
言語 | C++11 (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 21 ms / 1,000 ms |
コード長 | 3,080 bytes |
コンパイル時間 | 4,639 ms |
実行使用メモリ | 1,624 KB |
スコア | 40,509 |
最終ジャッジ日時 | 2018-05-26 15:55:50 |
ジャッジサーバーID (参考情報) |
judge9 / |
純コード判定しない問題か言語 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 32 |
ソースコード
#include <bits/stdc++.h>using namespace std;constexpr double TIME_LIMIT = 0.9;constexpr double CYCLES_PER_SEC_INV = 1.0 / (2.8 * 1e9);constexpr double XORSHIFT_INV = 1.0 / (1ULL << 32);double getTime() {uint32_t low, high;__asm__ volatile ("rdtsc" : "=a" (low), "=d" (high));uint64_t cycle = ((uint64_t)low) | ((uint64_t)high << 32);return cycle * CYCLES_PER_SEC_INV;}double getRand() {static uint32_t x = 123456789, y = 362436069,z = 521288629 ^ ((uint64_t)(getTime() / CYCLES_PER_SEC_INV)),w = 88675123 ^ ((uint64_t)(getTime() / CYCLES_PER_SEC_INV));uint32_t t = x ^ (x << 11); x = y; y = z; z = w;w = (w ^ (w >> 19)) ^ (t ^ (t >> 8));return w * XORSHIFT_INV;}constexpr int MAX_N = 60;int n;int k;vector<int> l;vector<bitset<MAX_N>> bsL;vector<bitset<MAX_N>> rowA;vector<bitset<MAX_N>> colA;vector<array<int, 4>> states;void input() {cin >> n >> k;l.resize(k);bsL.resize(k);for (int i = 0; i < k; i++) {cin >> l[i];for (int j = 0; j < l[i]; j++) {bsL[i][j] = 1;}}rowA.resize(n);colA.resize(n);for (int r = 0; r < n; r++) {string t;cin >> t;reverse(t.begin(), t.end());rowA[r] = bitset<MAX_N>(t);}for (int r = 0; r < n; r++) {for (int c = 0; c < n; c++) {colA[c][r] = rowA[r][c];}}}void greedy() {double startTime = getTime();for (int i = 0; i < k; i++) {int idx = (int)(getRand() * n);int bestDiff = 0;array<int, 4> bestState = {0, 0, (l[i] - 1), 0};for (int r = 0; r < n; r++) {for (int c = 0; c < n - (l[i] - 1); c++) {auto diff = rowA[r] & (bsL[i] << c);if (bestDiff < diff.count()) {bestDiff = diff.count();bestState = {r, c, r, c + (l[i] - 1)};}if (l[i] <= diff.count()) {break;}}}for (int c = 0; c < n; c++) {for (int r = 0; r < n - (l[i] - 1); r++) {auto diff = colA[c] & (bsL[i] << r);if (bestDiff < diff.count()) {bestDiff = diff.count();bestState = {r, c, r + (l[i] - 1), c};}if (l[i] <= diff.count()) {break;}}}states.emplace_back(bestState);for (int r = bestState[0]; r <= bestState[2]; r++) {for (int c = bestState[1]; c <= bestState[3]; c++) {rowA[r].flip(c);colA[c].flip(r);}}}fprintf(stderr, "greedy time:%f\n", getTime() - startTime);}void output() {for (int i = 0; i < k; i++) {for (int j = 0; j < 4; j++) {cout << (states[i][j] + 1) << (j < 3 ? ' ' : '\n');}}}int main() {input();greedy();output();return 0;}