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

• 問題: No.5002 stick xor
• ユーザー: hakomo
• 提出日時: 2018-05-29 19:29:31
• 言語: C++14 (gcc 12.3.0 + boost 1.83.0)
• 結果: AC
• 実行時間: 985 ms / 1,000 ms
• コード長: 14,128 bytes
• コンパイル時間: 35,354 ms
• 実行使用メモリ: 1,820 KB
• スコア: 52,535
• 最終ジャッジ日時: 2018-05-29 19:30:08
• ジャッジサーバーID （参考情報）: judge6 /

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

ソースコード

#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;
    int x, y, length, id;
    Rectangle() {}
    Rectangle(bool vertical, int x, int y, int length, int id)
        : vertical(vertical), x(x), y(y), length(length), id(id) {}
};

struct Line {
    bool vertical;
    int y;
    long long line;
    Line() {}
    Line(bool vertical, int y) : vertical(vertical), y(y) {}
};

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

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

inline void flip2(const Rectangle& r, unsigned i) {
    board[r.vertical][r.y] ^= ((1ll << r.length) - 1) << r.x;
    if (i - r.x < (unsigned)r.length)
        board[!r.vertical][i] ^= 1ll << 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] |= 1ll << x;
                board[1][x] |= 1ll << 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] & ((1ll << p.first) - 1) << x);
                            if (b < s) {
                                b = s;
                                n = { i, x, y };
                            }
                        }
                    }
                }
                lineToIndicies[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]);
    vector<array<Line, 2>> ne;
    int ni = -1;
    for (int i = 1; i < N * 2; ++i) {
        for (int j = 0; j < i; ++j) {
            ne.emplace_back(array<Line, 2>{ Line{ !!(i & 1), i >> 1 }, { !!(j & 1), j >> 1 } });
            if (ne.back()[0].vertical)
                swap(ne.back()[0], ne.back()[1]);
        }
    }
    random_shuffle(ne.begin(), ne.end(), rando);
    double heat = 0;
    for (int iter = -1; ; ) {
        if ((++iter & 0x7ff) == 0) {
            double p = 1 - (timer.time() - timer.t) / timer.limit;
            if (p < 0) break;
            constexpr double InitialHeat = 0.6;
            constexpr double FinalHeat = 1e-9;
            heat = 1 / (p * (InitialHeat - FinalHeat) + FinalHeat);
        }
        if (++ni == ne.size()) ni = 0;
        auto& lines = ne[ni];
        bool parallel = lines[0].vertical == lines[1].vertical;
        static vector<int> indicies;
        static vector<Rectangle> rectangles;
        indicies.clear();
        rectangles.clear();
        lines[0].line = board[lines[0].vertical][lines[0].y];
        lines[1].line = board[lines[1].vertical][lines[1].y];
        int s0, s1;
        {
            auto& p = lineToIndicies[lines[0].vertical][lines[0].y];
            auto& q = lineToIndicies[lines[1].vertical][lines[1].y];
            s0 = (int)p.size();
            s1 = (int)q.size();
            for (int n = min(3, s0 + s1); n--; ) {
                int i = rando.next(s0 + s1);
                if (i < s0) {
                    indicies.emplace_back(p[i]);
                    flip2(states[p[i]], parallel ? -1 : lines[1].y);
                    swap(p[i], p[--s0]);
                } else {
                    i -= (int)s0;
                    indicies.emplace_back(q[i]);
                    flip2(states[q[i]], parallel ? -1 : lines[0].y);
                    swap(q[i], q[--s1]);
                }
            }
        }
        for (int i : indicies) {
            auto& r = states[i];
            long long bn = -1 << 30;
            rectangles.emplace_back(r);
            auto& br = rectangles.back();
            for (auto& l : lines) {
                long long line = board[l.vertical][l.y];
                long long mask = (1ll << r.length) - 1;
                for (int x = r.length; x <= N; x += 2) {
                    long long n = __builtin_ctzll(line);
                    x += (int)n;
                    line >>= n;
                    n = __builtin_popcountll(line & mask);
                    if (bn < n) {
                        bn = n;
                        br.vertical = l.vertical;
                        br.y = l.y;
                        br.x = min(N, x) - r.length;
                        if (bn == r.length) break;
                    }
                    line >>= 2;
                }
                if (bn == r.length) break;
            }
            flip2(br, parallel ? -1 : lines[!br.vertical].y);
        }
        for (int last = -1; ; ) {
            bool updated = false;
            for (auto& r : rectangles) {
                long long bn = board[r.vertical][r.y] & ((1ll << r.length) - 1) << r.x;
                if (bn == 0) 
                    if (last == r.id) break;
                    else continue;
                long long cn = bn = r.length - __builtin_popcountll(bn);
                flip2(r, parallel ? -1 : lines[!r.vertical].y);
                for (auto& l : lines) {
                    long long line = board[l.vertical][l.y];
                    long long mask = (1ll << r.length) - 1;
                    for (int x = r.length; x <= N; x += 2) {
                        long long n = __builtin_ctzll(line);
                        x += (int)n;
                        line >>= n;
                        n = __builtin_popcountll(line & mask);
                        if (bn < n) {
                            bn = n;
                            r.vertical = l.vertical;
                            r.y = l.y;
                            r.x = min(N, x) - r.length;
                        }
                        line >>= 2;
                    }
                }
                flip2(r, parallel ? -1 : lines[!r.vertical].y);
                if (bn != cn) {
                    updated = true;
                    last = r.id;
                } else if (last == r.id) break;
            }
            if (!updated) break;
        }
        int diff = (int)(__builtin_popcountll(lines[0].line) + __builtin_popcountll(lines[1].line)
            - (!parallel && lines[0].line >> lines[1].y & 1)
            - __builtin_popcountll(board[lines[0].vertical][lines[0].y])
            - __builtin_popcountll(board[lines[1].vertical][lines[1].y])
            + (!parallel && board[lines[0].vertical][lines[0].y] >> lines[1].y & 1));
        if (rando.nextDouble() < exp(diff * heat)) {
            score += diff;
            lineToIndicies[lines[0].vertical][lines[0].y].resize(s0);
            lineToIndicies[lines[1].vertical][lines[1].y].resize(s1);
            lines[0].line = lines[1].line = 0;
            for (int i = 0; i < (int)indicies.size(); ++i) {
                auto& r = states[indicies[i]];
                for (int j = 0; j < 2; ++j) {
                    int k = r.vertical == lines[1].vertical && r.y == lines[1].y;
                    lines[k].line ^= ((1ll << r.length) - 1) << r.x;
                    if (!parallel && (unsigned)lines[!r.vertical].y - r.x < (unsigned)r.length)
                        lines[k].line ^= 1ll << lines[!r.vertical].y;
                    if (j == 0)
                        r = rectangles[i];
                    else
                        lineToIndicies[r.vertical][r.y].emplace_back(indicies[i]);
                }
            }
            for (auto& l : lines) {
                long long mask = 1ll << l.y;
                while (l.line) {
                    long long x = __builtin_ctzll(l.line);
                    board[!l.vertical][x] ^= mask;
                    l.line ^= 1ll << x;
                }
            }
            if (bestScore < score) {
                bestScore = score;
                bestStates = states;
            }
        } else {
            board[lines[0].vertical][lines[0].y] = lines[0].line;
            board[lines[1].vertical][lines[1].y] = lines[1].line;
        }
    }
    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();
            } else 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;
}