結果

問題 No.5002 stick xor
ユーザー masaktmasakt
提出日時 2018-05-26 16:45:23
言語 C++11
(gcc 11.4.0)
結果
AC  
実行時間 28 ms / 1,000 ms
コード長 3,247 bytes
コンパイル時間 4,247 ms
実行使用メモリ 1,600 KB
スコア 39,729
最終ジャッジ日時 2018-05-26 16:45:35
ジャッジサーバーID
（参考情報） 		judge8 /
純コード判定しない問題か言語
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 19 ms
1,596 KB
testcase_01 AC 19 ms
1,596 KB
testcase_02 AC 20 ms
1,596 KB
testcase_03 AC 20 ms
1,596 KB
testcase_04 AC 19 ms
1,592 KB
testcase_05 AC 18 ms
1,592 KB
testcase_06 AC 18 ms
1,596 KB
testcase_07 AC 20 ms
1,592 KB
testcase_08 AC 20 ms
1,592 KB
testcase_09 AC 19 ms
1,596 KB
testcase_10 AC 19 ms
1,600 KB
testcase_11 AC 20 ms
1,596 KB
testcase_12 AC 27 ms
1,592 KB
testcase_13 AC 26 ms
1,596 KB
testcase_14 AC 21 ms
1,592 KB
testcase_15 AC 21 ms
1,596 KB
testcase_16 AC 21 ms
1,596 KB
testcase_17 AC 20 ms
1,596 KB
testcase_18 AC 19 ms
1,596 KB
testcase_19 AC 19 ms
1,592 KB
testcase_20 AC 20 ms
1,596 KB
testcase_21 AC 20 ms
1,596 KB
testcase_22 AC 26 ms
1,592 KB
testcase_23 AC 19 ms
1,592 KB
testcase_24 AC 28 ms
1,596 KB
testcase_25 AC 26 ms
1,592 KB
testcase_26 AC 19 ms
1,592 KB
testcase_27 AC 20 ms
1,596 KB
testcase_28 AC 19 ms
1,596 KB
testcase_29 AC 19 ms
1,600 KB
testcase_30 AC 19 ms
1,596 KB
testcase_31 AC 19 ms
1,596 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#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<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 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();
    output();
    return 0;
}
0