結果

問題 No.5002 stick xor
ユーザー masaktmasakt
提出日時 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
権限があれば一括ダウンロードができます

ソースコード

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