#261198 (C++14) No.5002 stick xor

提出ソース

結果

問題	No.5002 stick xor
ユーザー	hakomo
提出日時	2018-05-28 22:33:45
言語	C++14 (gcc 12.3.0 + boost 1.83.0)
結果	AC
実行時間	987 ms / 1,000 ms
コード長	13,360 bytes
コンパイル時間	35,295 ms
実行使用メモリ	1,628 KB
スコア	49,023
最終ジャッジ日時	2018-05-28 22:34:22
ジャッジサーバーID （参考情報）	judge8 /
	純コード判定しない問題か言語

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	987 ms 1,620 KB
testcase_01	AC	985 ms 1,620 KB
testcase_02	AC	985 ms 1,624 KB
testcase_03	AC	987 ms 1,624 KB
testcase_04	AC	985 ms 1,620 KB
testcase_05	AC	986 ms 1,620 KB
testcase_06	AC	987 ms 1,620 KB
testcase_07	AC	986 ms 1,620 KB
testcase_08	AC	987 ms 1,628 KB
testcase_09	AC	986 ms 1,616 KB
testcase_10	AC	985 ms 1,624 KB
testcase_11	AC	984 ms 1,624 KB
testcase_12	AC	987 ms 1,624 KB
testcase_13	AC	987 ms 1,624 KB
testcase_14	AC	983 ms 1,624 KB
testcase_15	AC	987 ms 1,620 KB
testcase_16	AC	985 ms 1,620 KB
testcase_17	AC	984 ms 1,624 KB
testcase_18	AC	987 ms 1,620 KB
testcase_19	AC	987 ms 1,624 KB
testcase_20	AC	985 ms 1,624 KB
testcase_21	AC	986 ms 1,628 KB
testcase_22	AC	985 ms 1,620 KB
testcase_23	AC	983 ms 1,620 KB
testcase_24	AC	985 ms 1,620 KB
testcase_25	AC	985 ms 1,624 KB
testcase_26	AC	986 ms 1,624 KB
testcase_27	AC	983 ms 1,620 KB
testcase_28	AC	986 ms 1,620 KB
testcase_29	AC	986 ms 1,620 KB
testcase_30	AC	986 ms 1,620 KB
testcase_31	AC	986 ms 1,620 KB

権限があれば一括ダウンロードができます

ソースコード

raw source code

#include <algorithm>
#include <array>
#include <chrono>
#include <cmath>
#include <iostream>
#include <random>
#include <vector>
using namespace std;
#define U(v) cerr << #v << ": " << (v) << endl

constexpr int dx[] = { 1, 0, -1, 0 };
constexpr int dy[] = { 0, 1, 0, -1 };

class timer {
    vector<timer> timers;
    int n = 0;
public:
    double limit = 0.98;
    double t = 0;
    timer() {}
    timer(int size) : timers(size) {}
    bool elapses() const {
        return time() - t > limit;
    }
    void measure() {
        t = time() - t;
        ++n;
    }
    void measure(char id) {
        timers[id].measure();
    }
    void print() {
        if (n % 2)
            measure();
        for (int i = 0; i < 128; ++i) {
            if (timers[i].n)
                cerr << (char)i << ' ' << timers[i].t << 's' << endl;
        }
        cerr << "  " << t << 's' << endl;
    }
    static double time() {
#ifdef LOCAL
        return __rdtsc() / 3.3e9;
#else
        return chrono::duration_cast<chrono::milliseconds>(chrono::system_clock::now().time_since_epoch()).count() / 1000.0;
#endif
    }
} timer(128);

class {
    //unsigned y = 2463534242;
    unsigned y = random_device()();
public:
    unsigned next() {
        return y ^= (y ^= (y ^= y << 13) >> 17) << 5;
    }
    int next(int b) {
        return next() % b;
    }
    int next(int a, int b) {
        return next(b - a) + a;
    }
    double nextDouble(double b = 1) {
        return b * next() / 4294967296.0;
    }
    double nextDouble(double a, double b) {
        return nextDouble(b - a) + a;
    }
    int operator() (int b) {
        return next(b);
    }
} rando;

struct Rectangle {
    bool vertical;
    char x, y, length;
    short id;
    Rectangle() {}
    Rectangle(bool vertical, char x, char y, char length, short id)
        : vertical(vertical), x(x), y(y), length(length), id(id) {}
};

constexpr int N = 60;
constexpr int K = 500;
int L[K];
bool A[N][N];
unsigned long long board[2][N];
vector<Rectangle> states, bestStates;
int score, bestScore;
vector<int> p2i[2][N];

inline void flip(const Rectangle& r) {
    board[r.vertical][r.y] ^= ((1ull << r.length) - 1) << r.x;
    unsigned long long mask = 1ull << r.y;
    for (int x = r.x; x < r.x + r.length; ++x)
        board[!r.vertical][x] ^= mask;
}

inline void flip2(const Rectangle& r, int i) {
    board[r.vertical][r.y] ^= ((1ull << r.length) - 1) << r.x;
    if ((unsigned)i - r.x < (unsigned)r.length)
        board[!r.vertical][i] ^= 1ull << r.y;
}

int main(int argc, char** argv) {
    timer.measure();
    {
        int k;
        cin >> k >> k;
        for (int i = 0; i < K; ++i)
            cin >> L[i];
        char s[N + 1];
        for (int y = 0; y < N; ++y) {
            cin >> s;
            for (int x = 0; x < N; ++x)
                A[y][x] = s[x] == '1';
        }
    }
    for (int y = 0; y < N; ++y) {
        for (int x = 0; x < N; ++x) {
            if (A[y][x]) {
                board[0][y] |= 1ull << x;
                board[1][x] |= 1ull << y;
            } else {
                --score;
            }
        }
    }
    vector<int> a1, a2;
    {
        pair<int, int> a[K];
        for (int i = 0; i < K; ++i)
            a[i] = { L[i], i };
        sort(rbegin(a), rend(a));
        for (auto& p : a) {
            if (p.first > 2) {
                long long b = -1 << 30;
                array<int, 3> n;
                for (int i = 0; i < 2; ++i) {
                    for (int y = 0; y < N; ++y) {
                        for (int x = 0; x < N - p.first + 1; ++x) {
                            long long s = __builtin_popcountll(board[i][y] & ((1ull << p.first) - 1) << x);
                            if (b < s) {
                                b = s;
                                n = { i, x, y };
                            }
                        }
                    }
                }
                p2i[n[0]][n[2]].emplace_back((int)states.size());
                states.emplace_back(!!n[0], n[1], n[2], p.first, p.second);
                flip(states.back());
            } else {
                (p.first == 1 ? a1 : a2).emplace_back(p.second);
                score += p.first;
            }
        }
    }
    for (int y = 0; y < N; ++y)
        score += N - (int)__builtin_popcountll(board[0][y]);
    bestScore = score;
    bestStates = states;
    double heat = 0;
    for (int iter = -1; ; ) {
        if ((++iter & 0x1ff) == 0) {
            //double p = 1 - iter / 1000000.0;
            double p = 1 - (timer.time() - timer.t) / timer.limit;
            if (p < 0) {
                //U(iter);
                break;
            }
            constexpr double InitialHeat = 0.7;
            constexpr double FinalHeat = 1e-9;
            heat = 1 / (p * (InitialHeat - FinalHeat) + FinalHeat);
        }
        pair<bool, int> a[2]{ { !(rando.next() & 1), rando.next(N) } };
        do {
            a[1] = { !(rando.next() & 1), rando.next(N) };
        } while (a[0] == a[1]);
        if (a[0].first)
            swap(a[0], a[1]);
        bool par = a[0].first == a[1].first;
        int curr = (int)__builtin_popcountll(board[a[0].first][a[0].second])
            + (int)__builtin_popcountll(board[a[1].first][a[1].second])
            - (!par && board[a[0].first][a[0].second] >> a[1].second & 1);
        static vector<int> is;
        static vector<Rectangle> rs;
        is.clear();
        rs.clear();
        for (int h = 0; h < 2; ++h) {
            auto& p = a[h];
            for (int i : p2i[p.first][p.second]) {
                is.emplace_back(i);
                flip2(states[i], par ? -1 : a[1 - h].second);
            }
        }
        random_shuffle(is.begin(), is.end(), rando);        
        for (int i : is) {
            auto& r = states[i];
            long long b = -1 << 30;
            pair<bool, int> bp;
            int bx;
            for (auto& p : a) {
                unsigned long long bi = board[p.first][p.second];
                unsigned long long ma = (1ull << r.length) - 1;
                for (int x = 0; x < N - r.length + 1; ++x) {
                    long long s = __builtin_popcountll(bi & ma);
                    if (b < s) {
                        b = s;
                        bp = p;
                        bx = x;
                        if (b == r.length) break;
                    }
                    bi >>= 1;
                }
                if (b == r.length) break;
            }
            rs.emplace_back(bp.first, bx, bp.second, r.length, r.id);
            flip2(rs.back(), par ? -1 : a[!bp.first].second);
        }
        for (int last = -1; ; ) {
            bool updated = false;
            for (int h = 0; h < (int)rs.size(); ++h) {
                auto& r = rs[h];
                long long c = board[r.vertical][r.y] & ((1ull << r.length) - 1) << r.x;
                if (c == 0) continue;
                flip2(r, par ? -1 : a[!r.vertical].second);
                long long b = c = r.length - __builtin_popcountll(c);
                pair<bool, int> bp;
                int bx;
                for (auto& p : a) {
                    unsigned long long bi = board[p.first][p.second];
                    unsigned long long ma = (1ull << r.length) - 1;
                    for (int x = 0; x < N - r.length + 1; ++x) {
                        long long s = __builtin_popcountll(bi & ma);
                        if (b < s) {
                            b = s;
                            bp = p;
                            bx = x;
                        }
                        bi >>= 1;
                    }
                }
                if (b != c) {
                    last = h;
                    updated = true;
                    r.vertical = bp.first;
                    r.x = bx;
                    r.y = bp.second;
                } else if (last == h) {
                    flip2(r, par ? -1 : a[!r.vertical].second);
                    break;
                }
                flip2(r, par ? -1 : a[!r.vertical].second);
            }
            if (!updated) break;
        }
        int diff = curr - ((int)__builtin_popcountll(board[a[0].first][a[0].second])
            + (int)__builtin_popcountll(board[a[1].first][a[1].second])
            - (!par && board[a[0].first][a[0].second] >> a[1].second & 1));
        if (rando.nextDouble() < exp(diff * heat)) {
            score += diff;
            for (int i = 0; i < (int)is.size(); ++i) {
                {
                    auto& r = states[is[i]];
                    unsigned long long mask = 1ull << r.y;
                    if (!par && (unsigned)a[!r.vertical].second - r.x < (unsigned)r.length)
                        board[!r.vertical][a[!r.vertical].second] ^= mask;
                    for (int x = r.x; x < r.x + r.length; ++x)
                        board[!r.vertical][x] ^= mask;
                }
                {
                    auto& r = rs[i];
                    unsigned long long mask = 1ull << r.y;
                    if (!par && (unsigned)a[!r.vertical].second - r.x < (unsigned)r.length)
                        board[!r.vertical][a[!r.vertical].second] ^= mask;
                    for (int x = r.x; x < r.x + r.length; ++x)
                        board[!r.vertical][x] ^= mask;
                }
            }
            for (auto& p : a)
                p2i[p.first][p.second].clear();
            for (int i = 0; i < (int)is.size(); ++i) {
                states[is[i]] = rs[i];
                p2i[rs[i].vertical][rs[i].y].emplace_back(is[i]);
            }
            if (bestScore < score) {
                bestScore = score;
                bestStates = states;
            }
        } else {
            for (int i = 0; i < (int)is.size(); ++i) {
                flip2(states[is[i]], par ? -1 : a[!states[is[i]].vertical].second);
                flip2(rs[i], par ? -1 : a[!rs[i].vertical].second);
            }
        }
    }
    score = bestScore;
    states.swap(bestStates);
    for (auto& r : states) {
        if (r.vertical) {
            for (int x = r.x; x < r.x + r.length; ++x)
                A[x][r.y] ^= 1;
        } else {
            for (int x = r.x; x < r.x + r.length; ++x)
                A[r.y][x] ^= 1;
        }
    }
    for (int y = 0; y < N; ++y) {
        for (int x = 0; x < N; ++x) {
            if (y && A[y][x] && A[y - 1][x] && a2.size()) {
                A[y][x] = A[y - 1][x] = false;
                states.emplace_back(true, y - 1, x, 2, a2.back());
                a2.pop_back();
            }
            if (x && A[y][x] && A[y][x - 1] && a2.size()) {
                A[y][x] = A[y][x - 1] = false;
                states.emplace_back(false, x - 1, y, 2, a2.back());
                a2.pop_back();
            }
        }
    }
    for (int y = 0; y < N; ++y) {
        for (int x = 0; x < N; ++x) {
            if (A[y][x]) continue;
            for (int i = 1; i < 4; ++i) {
                int x2 = x + dx[i];
                int y2 = y + dy[i];
                if (x2 < 0 || N <= x2 || y2 < 0 || N <= y2 || !A[y2][x2]) continue;
                for (int j = 0; j < i; ++j) {
                    int x3 = x + dx[j];
                    int y3 = y + dy[j];
                    if (x3 < 0 || N <= x3 || y3 < 0 || N <= y3 || !A[y3][x3] || a2.size() < 2) continue;
                    A[y2][x2] = A[y3][x3] = false;
                    score -= 2;
                    if (i % 2)
                        states.emplace_back(true, min(y, y2), x, 2, a2.back());
                    else
                        states.emplace_back(false, min(x, x2), y, 2, a2.back());
                    a2.pop_back();
                    if (j % 2)
                        states.emplace_back(true, min(y, y3), x, 2, a2.back());
                    else
                        states.emplace_back(false, min(x, x3), y, 2, a2.back());
                    a2.pop_back();
                    break;
                }
            }
        }
    }
    score -= (int)a2.size() * 2;
    for (int y = 0; y < N && a2.size(); ++y) {
        for (int x = 0; x < N && a2.size(); ++x) {
            if (y && A[y][x] != A[y - 1][x]) {
                for (; a2.size(); a2.pop_back()) {
                    A[y][x] ^= 1;
                    A[y - 1][x] ^= 1;
                    states.emplace_back(true, y - 1, x, 2, a2.back());
                }
            }
            if (x && A[y][x] != A[y][x - 1]) {
                for (; a2.size(); a2.pop_back()) {
                    A[y][x] ^= 1;
                    A[y][x - 1] ^= 1;
                    states.emplace_back(false, x - 1, y, 2, a2.back());
                }
            }
        }
    }
    for (int y = 0; y < N; ++y) {
        for (int x = 0; x < N; ++x) {
            if (A[y][x] && a1.size()) {
                states.emplace_back(false, x, y, 1, a1.back());
                a1.pop_back();
            }
        }
    }
    sort(states.begin(), states.end(), [](const Rectangle& a, const Rectangle& b) {
        return a.id < b.id;
    });
    for (auto& r : states) {
        if (r.vertical) {
            cout << r.x + 1 << ' ' << r.y + 1 << ' ' << r.x + r.length << ' ' << r.y + 1 << endl;
        } else {
            cout << r.y + 1 << ' ' << r.x + 1 << ' ' << r.y + 1 << ' ' << r.x + r.length << endl;
        }
    }
    return 0;
}

yukicoder

結果

テストケース

ソースコード