結果

問題 No.5002 stick xor
コンテスト
ユーザー masakt
提出日時 2018-05-26 17:44:04
言語 C++11（廃止可能性あり）
(gcc 13.3.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 /
純コード判定しない問題か言語
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 32
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#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;
}
0