結果
問題 | No.5002 stick xor |
ユーザー | masakt |
提出日時 | 2018-05-26 17:44:04 |
言語 | C++11 (gcc 11.4.0) |
結果 |
AC
|
実行時間 | 998 ms / 1,000 ms |
コード長 | 4,807 bytes |
コンパイル時間 | 36,669 ms |
実行使用メモリ | 1,604 KB |
スコア | 40,695 |
最終ジャッジ日時 | 2018-05-26 17:44:43 |
ジャッジサーバーID (参考情報) |
judge8 / |
純コード判定しない問題か言語 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 993 ms
1,600 KB |
testcase_01 | AC | 996 ms
1,596 KB |
testcase_02 | AC | 994 ms
1,600 KB |
testcase_03 | AC | 991 ms
1,600 KB |
testcase_04 | AC | 991 ms
1,596 KB |
testcase_05 | AC | 993 ms
1,600 KB |
testcase_06 | AC | 997 ms
1,600 KB |
testcase_07 | AC | 984 ms
1,600 KB |
testcase_08 | AC | 991 ms
1,600 KB |
testcase_09 | AC | 986 ms
1,600 KB |
testcase_10 | AC | 995 ms
1,600 KB |
testcase_11 | AC | 990 ms
1,600 KB |
testcase_12 | AC | 991 ms
1,604 KB |
testcase_13 | AC | 998 ms
1,600 KB |
testcase_14 | AC | 994 ms
1,600 KB |
testcase_15 | AC | 991 ms
1,596 KB |
testcase_16 | AC | 989 ms
1,596 KB |
testcase_17 | AC | 987 ms
1,600 KB |
testcase_18 | AC | 992 ms
1,596 KB |
testcase_19 | AC | 995 ms
1,600 KB |
testcase_20 | AC | 987 ms
1,596 KB |
testcase_21 | AC | 996 ms
1,600 KB |
testcase_22 | AC | 997 ms
1,600 KB |
testcase_23 | AC | 996 ms
1,600 KB |
testcase_24 | AC | 996 ms
1,596 KB |
testcase_25 | AC | 996 ms
1,600 KB |
testcase_26 | AC | 992 ms
1,596 KB |
testcase_27 | AC | 992 ms
1,600 KB |
testcase_28 | AC | 991 ms
1,596 KB |
testcase_29 | AC | 998 ms
1,604 KB |
testcase_30 | AC | 986 ms
1,596 KB |
testcase_31 | AC | 992 ms
1,596 KB |
ソースコード
#include <bits/stdc++.h> using namespace std; constexpr double TIME_LIMIT = 0.9; constexpr double CYCLES_PER_SEC_INV = 1.0 / (2.8 * 1e9); 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; } constexpr int MAX_N = 60; int n; int k; vector<int> l; vector<bitset<MAX_N>> bsL; vector<tuple<int, int>> orderL; 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); orderL.resize(k); states.resize(k); for (int i = 0; i < k; i++) { cin >> l[i]; for (int j = 0; j < l[i]; j++) { bsL[i][j] = 1; } orderL[i] = make_tuple(l[i], i); } sort(orderL.rbegin(), orderL.rend()); 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 initialSolution() { double startTime = getTime(); for (auto& e: orderL) { int bestDiff = 0; array<int, 4> bestState = {0, 0, (get<0>(e) - 1), 0}; for (int r = 0; r < n; r++) { for (int c = 0; c < n - (get<0>(e) - 1); c++) { auto diff = rowA[r] & (bsL[get<1>(e)] << c); if (bestDiff < diff.count()) { bestDiff = diff.count(); bestState = {r, c, r, c + (get<0>(e) - 1)}; } if (get<0>(e) <= diff.count()) { break; } } } for (int c = 0; c < n; c++) { for (int r = 0; r < n - (get<0>(e) - 1); r++) { auto diff = colA[c] & (bsL[get<1>(e)] << r); if (bestDiff < diff.count()) { bestDiff = diff.count(); bestState = {r, c, r + (get<0>(e) - 1), c}; } if (get<0>(e) <= diff.count()) { break; } } } states[get<1>(e)] = 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, "initialSolution time:%f\n", getTime() - startTime); } void greedy() { double startTime = getTime(); int iter = 0; do { iter++; for (auto& e: orderL) { int bestDiff = 0; array<int, 4> bestState = states[get<1>(e)]; for (int r = bestState[0]; r <= bestState[2]; r++) { for (int c = bestState[1]; c <= bestState[3]; c++) { bestDiff += rowA[r][c] ? -1 : 1; rowA[r].flip(c); colA[c].flip(r); } } for (int r = 0; r < n; r++) { for (int c = 0; c < n - (get<0>(e) - 1); c++) { auto diff = rowA[r] & (bsL[get<1>(e)] << c); if (bestDiff < diff.count()) { bestDiff = diff.count(); bestState = {r, c, r, c + (get<0>(e) - 1)}; } if (get<0>(e) <= diff.count()) { break; } } } for (int c = 0; c < n; c++) { for (int r = 0; r < n - (get<0>(e) - 1); r++) { auto diff = colA[c] & (bsL[get<1>(e)] << r); if (bestDiff < diff.count()) { bestDiff = diff.count(); bestState = {r, c, r + (get<0>(e) - 1), c}; } if (get<0>(e) <= diff.count()) { break; } } } states[get<1>(e)] = 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); } } } } while (TIME_LIMIT >= getTime() - startTime); fprintf(stderr, "greedy iter:%d,time:%f\n", iter, 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(); initialSolution(); greedy(); output(); return 0; }