結果

問題 No.5002 stick xor
コンテスト
ユーザー zenito9970
提出日時 2018-06-01 22:18:36
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 910 ms / 1,000 ms
コード長 4,646 bytes
コンパイル時間 33,646 ms
実行使用メモリ 1,596 KB
スコア 37,867
最終ジャッジ日時 2018-06-01 22:19:12
ジャッジサーバーID
（参考情報） 		judge8 /
純コード判定しない問題か言語
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 32
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define rep(i,n) FOR(i,0,n)
#define repr(i,n) for(int i=(n)-1;0<=i;--i)
#define each(e,v) for(auto&& e:(v))
#define all(v) begin(v),end(v)
#define dump(x) cerr<<#x<<": "<<(x)<<endl
using namespace std;
using vint = vector<int>;
using ll = long long;
using vll = vector<ll>;
template <class T> void chmin(T& a, const T& b) { a = min(a, b); }
template <class T> void chmax(T& a, const T& b) { a = max(a, b); }

namespace Timer {
    using namespace std::chrono;
    high_resolution_clock::time_point start_time;
    inline void init() {
        start_time = high_resolution_clock::now();
    }
    inline int now() {
        auto now = high_resolution_clock::now();
        auto t = now - start_time;
        return duration_cast<milliseconds>(t).count();
    }
    inline bool check(int limit) {
        return now() < limit;
    }
}

struct Data {
    bool isH;
    int x, y;
};

void output(int l, Data d) {
    int eX = d.isH ? d.x : (d.x + l - 1);
    int eY = d.isH ? (d.y + l - 1) : d.y;
    cout << d.y+1 << " " << d.x+1 << " " << eY+1 << " " << eX+1 << endl;
}

int main() {
    Timer::init();
    int n, k; cin >> n >> k;
    vint L(k);
    rep(i, k) cin >> L[i];
    vector<vint> A(n, vint(n));
    rep(y, n) rep(x, n) { char c; cin >> c; A[y][x] = c == '1'; }

    int initialScore = [&]() {
        int score = 0;
        rep(y, n) rep(x, n) if(A[y][x] % 2 == 0) score++;
        return score;
    }();
    dump(initialScore);

    cerr << "rank of L" << endl;
    vector<pair<int, int>> rankL(k);
    rep(i, k) rankL[i] = make_pair(L[i], i);
    sort(all(rankL)); reverse(all(rankL));

    cerr << "random" << endl;
    mt19937 mt(random_device{}());
    vector<Data> data(k);
    rep(i, k) {
        data[i].isH = false;
        data[i].x = uniform_int_distribution<>(0, n - L[i])(mt);
        data[i].y = uniform_int_distribution<>(0, n-1)(mt);
        FOR(tx, data[i].x, data[i].x + L[i]) A[data[i].y][tx]++;
    }
    
    int cycle = 0, cntAccept = 0;
    vector<Data> bestData = data;

    cerr << "while" << endl;
    /*
    rep(ck, k) {
    /*/
    while(Timer::check(900)) {
        cycle++;
        const int i = cycle % k;
        const int ck = rankL[i].second;
        // const int ck = uniform_int_distribution<>(0, k-1)(mt);
    //*/
        const int l = L[ck];
        int bestX = data[ck].x, bestY = data[ck].y;
        bool bestR = data[ck].isH;

        if(bestR) FOR(ty, bestY, bestY + l) A[ty][bestX]--;
        else      FOR(tx, bestX, bestX + l) A[bestY][tx]--;

        int bestDscore = 0;
        rep(y, n) {
            rep(x, n - l) {
                int dscore = 0;
                if(A[y][x] % 2 == 0) continue;
                if(A[y][x+l-1] % 2 == 0) continue;
                FOR(tx, x, x + l) {
                    A[y][tx]++;
                    if(A[y][tx] % 2 == 0) {
                        dscore++;
                        // if(tx == x + l - 1) dscore += 4;
                    }
                    else dscore--;
                }
                if(bestDscore < dscore) {
                    bestDscore = dscore;
                    bestX = x; bestY = y;
                    bestR = false;
                }
                FOR(tx, x, x + l) A[y][tx]--;
            }
        }
        rep(y, n - l) {
            rep(x, n) {
                int dscore = 0;
                if(A[y][x] % 2 == 0) continue;
                if(A[y+l-1][x] % 2 == 0) continue;
                FOR(ty, y, y + l) {
                    A[ty][x]++;
                    if(A[ty][x] % 2 == 0) {
                        dscore++;
                        // if(ty == y + l - 1) dscore += 4;
                    }
                    else dscore--;
                }
                if(bestDscore < dscore) {
                    bestDscore = dscore;
                    bestX = x; bestY = y;
                    bestR = true;
                }
                FOR(ty, y, y + l) A[ty][x]--;
            }
        }
        // dump(ck); dump(bestX); dump(bestY);

        if(bestR) FOR(ty, bestY, bestY + l) A[ty][bestX]++;
        else      FOR(tx, bestX, bestX + l) A[bestY][tx]++;

        data[ck].x = bestX;
        data[ck].y = bestY;
        data[ck].isH = bestR;
    }

    bestData = data;

    cerr << "output" << endl;
    rep(i, k) output(L[i], bestData[i]);

    int lastScore = [&]() {
        int score = 0;
        rep(y, n) rep(x, n) if(A[y][x] % 2 == 0) score++;
        return score;
    }();

    dump(cycle);
    dump(cntAccept);
    cerr << "score: " << (lastScore - initialScore) << endl;
    dump(Timer::now());

    return 0;
}
0