結果

問題 No.5002 stick xor
ユーザー zenito9970zenito9970
提出日時 2018-05-27 01:45:01
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 906 ms / 1,000 ms
コード長 6,491 bytes
コンパイル時間 33,717 ms
実行使用メモリ 1,624 KB
スコア 23,897
最終ジャッジ日時 2018-05-27 01:48:03
ジャッジサーバーID
（参考情報） 		judge6 /
純コード判定しない問題か言語
このコードへのチャレンジ
（要ログイン）

テストケース

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

ソースコード

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

#define imosPW(imos,x,y,l) do{\
    (imos)[(y)][(x)]++; \
    (imos)[(y)][(x)+(l)]--; \
    (imos)[(y)+1][(x)]--; \
    (imos)[(y)+1][(x)+(l)]++; } while(0);

#define imosMW(imos,x,y,l) do{\
    (imos)[(y)][(x)]--; \
    (imos)[(y)][(x)+(l)]++; \
    (imos)[(y)+1][(x)]++; \
    (imos)[(y)+1][(x)+(l)]--; } while(0);

#define imosPH(imos,x,y,l) do{\
    (imos)[(y)][(x)]++; \
    (imos)[(y)+(l)][(x)]--; \
    (imos)[(y)][(x)+1]--; \
    (imos)[(y)+(l)][(x)+1]++; } while(0);

#define imosMH(imos,x,y,l) do{\
    (imos)[(y)][(x)]--; \
    (imos)[(y)+(l)][(x)]++; \
    (imos)[(y)][(x)+1]++; \
    (imos)[(y)+(l)][(x)+1]--; } while(0);


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

// vector<vint> imosX2grid(vector<vint> imos) {
//     const int n = imos.size();
//     rep(y, n) rep(x, n-1) {
//         imos[y][x+1] += imos[y][x];
//     }
//     return imos;
// }

// int calcScore(const vector<vint>& grid) {
//     const int n = grid.size();
//     int cnt = 0;
//     rep(y, n) rep(x, n) if(grid[y][x] % 2 == 0) cnt++;
//     return cnt;
// }

int calcScore(const vector<vint>& A, vector<vint> imos) {
    const int n = A.size();
    rep(y, n) rep(x, n) imos[y][x+1] += imos[y][x];
    rep(x, n) rep(y, n) imos[y+1][x] += imos[y][x];
    int cnt = 0;
    rep(y, n) rep(x, n) if((A[y][x] + imos[y][x]) % 2 == 0) cnt++;
    return cnt;
}

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'; }
    
    vector<vint> imos(n+1, vint(n+1, 0));
    int initialScore = calcScore(A, imos);
    dump(initialScore);

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

    vector<Data> bestData = data;
    int bestScore = -1e9;
    constexpr double paramA = 1;
    constexpr double paramB = 4;
    constexpr double initTemp = 100;

    cerr << "while" << endl;
    while(Timer::check(900)) {
        cycle++;
        // const double progress = (cycle + 0.5) / Num;
        const double progress = Timer::now() / 900.0;
        const double T = initTemp * pow(1 - progress, paramA) * exp2(-progress * paramB);

        // nextStep
        // int beforeScore = calcScore(A, imos);
        // int rk = uniform_int_distribution<>(0, k-1)(mt);
        int rk = cycle % k;
        bool rotateMode = uniform_int_distribution<>(0, 1)(mt) == 0;
        int rx, ry;

        if(rotateMode) {
            if(data[rk].isH) {
                if(n <= data[rk].x + L[rk]) continue;
                imosMH(imos, data[rk].x, data[rk].y, L[rk]);
                imosPW(imos, data[rk].x, data[rk].y, L[rk]);
            } else {
                if(n <= data[rk].y + L[rk]) continue;
                imosMW(imos, data[rk].x, data[rk].y, L[rk]);
                imosPH(imos, data[rk].x, data[rk].y, L[rk]);
            }
        } else {
            if(data[rk].isH) {
                rx = uniform_int_distribution<>(0, n-1)(mt);
                ry = uniform_int_distribution<>(0, n - L[rk])(mt);
                imosMH(imos, data[rk].x, data[rk].y, L[rk]);
                imosPH(imos, rx, ry, L[rk]);
            } else {
                rx = uniform_int_distribution<>(0, n - L[rk])(mt);
                ry = uniform_int_distribution<>(0, n-1)(mt);
                imosMW(imos, data[rk].x, data[rk].y, L[rk]);
                imosPW(imos, rx, ry, L[rk]);
            }
        }

        // imosMW(imos, data[rk].x, data[rk].y, L[rk]);
        // imosPW(imos, rx, ry, L[rk]);

        int newScore = calcScore(A, imos);
        if(beforeScore < newScore) { // || uniform_real_distribution<>(0, 1)(mt) <= exp(newScore - beforeScore) / T) {
            beforeScore = newScore;
            if(rotateMode) {
                data[rk].isH = !data[rk].isH;
            } else {
                data[rk].x = rx;
                data[rk].y = ry;
            }
            cntAccept++;

            if(bestScore < newScore) {
                bestScore = newScore;
                bestData = data;
            }
        } else {
            if(rotateMode) {
                if(data[rk].isH) {
                    imosMW(imos, data[rk].x, data[rk].y, L[rk]);
                    imosPH(imos, data[rk].x, data[rk].y, L[rk]);
                } else {
                    imosMH(imos, data[rk].x, data[rk].y, L[rk]);
                    imosPW(imos, data[rk].x, data[rk].y, L[rk]);
                }
            } else {
                if(data[rk].isH) {
                    imosMH(imos, data[rk].x, data[rk].y, L[rk]);
                    imosPH(imos, rx, ry, L[rk]);
                } else {
                    imosMW(imos, data[rk].x, data[rk].y, L[rk]);
                    imosPW(imos, rx, ry, L[rk]);
                }
            }
        }
    }

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

    dump(cycle);
    dump(cntAccept);
    cerr << "score: " << (bestScore - initialScore) << endl;

    return 0;
}
0