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

提出ソース

結果

問題	No.5002 stick xor
ユーザー	hakomo
提出日時	2018-05-26 20:36:20
言語	C++14 (gcc 12.3.0 + boost 1.83.0)
結果	AC
実行時間	987 ms / 1,000 ms
コード長	9,387 bytes
コンパイル時間	34,935 ms
実行使用メモリ	2,388 KB
スコア	47,051
最終ジャッジ日時	2018-05-26 20:36:56
ジャッジサーバーID （参考情報）	judge9 /
	純コード判定しない問題か言語

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

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	984 ms 2,388 KB
testcase_01	AC	984 ms 2,388 KB
testcase_02	AC	985 ms 2,388 KB
testcase_03	AC	984 ms 2,384 KB
testcase_04	AC	984 ms 2,384 KB
testcase_05	AC	985 ms 2,384 KB
testcase_06	AC	985 ms 2,384 KB
testcase_07	AC	984 ms 2,384 KB
testcase_08	AC	982 ms 2,384 KB
testcase_09	AC	984 ms 2,388 KB
testcase_10	AC	985 ms 2,384 KB
testcase_11	AC	984 ms 2,384 KB
testcase_12	AC	985 ms 2,380 KB
testcase_13	AC	984 ms 2,388 KB
testcase_14	AC	984 ms 2,384 KB
testcase_15	AC	984 ms 2,384 KB
testcase_16	AC	984 ms 2,388 KB
testcase_17	AC	985 ms 2,388 KB
testcase_18	AC	985 ms 2,388 KB
testcase_19	AC	985 ms 2,384 KB
testcase_20	AC	984 ms 2,384 KB
testcase_21	AC	984 ms 2,384 KB
testcase_22	AC	985 ms 2,384 KB
testcase_23	AC	984 ms 2,384 KB
testcase_24	AC	984 ms 2,388 KB
testcase_25	AC	984 ms 2,388 KB
testcase_26	AC	987 ms 2,384 KB
testcase_27	AC	986 ms 2,388 KB
testcase_28	AC	987 ms 2,388 KB
testcase_29	AC	985 ms 2,388 KB
testcase_30	AC	986 ms 2,388 KB
testcase_31	AC	985 ms 2,384 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

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;

constexpr int N = 60;
constexpr int K = 500;
int L[K];
bool A[N][N];
unsigned long long ls[N];
unsigned long long cs[N];
vector<array<int, 5>> states, bestStates;
int score, bestScore;
double ths[128];

inline void flip(const array<int, 5>& r, bool up) {
    if (r[2] != 1) {
        ls[r[1]] ^= ((1ull << r[2]) - 1) << r[0];
        if (up) {
            unsigned long long mask = 1ull << r[1];
            for (int x = r[0]; x < r[0] + r[2]; ++x)
                cs[x] ^= mask;
        }
    } else {
        cs[r[0]] ^= ((1ull << r[3]) - 1) << r[1];
        if (up) {
            unsigned long long mask = 1ull << r[0];
            for (int y = r[1]; y < r[1] + r[3]; ++y)
                ls[y] ^= mask;
        }
    }
}

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';
        }
    }
    //{
    //    mt19937 mt(atoi(argv[1]));
    //    for (int i = 0; i < K; ++i)
    //        L[i] = mt() % 25 + 1;
    //    for (int y = 0; y < N; ++y)
    //        for (int x = 0; x < N; ++x)
    //            A[y][x] = mt() % 2 == 1;
    //}

    for (int y = 0; y < N; ++y) {
        for (int x = 0; x < N; ++x) {
            if (A[y][x]) {
                ls[y] |= 1ull << x;
                cs[x] |= 1ull << y;
            } else {
                --score;
            }
        }
    }
    vector<int> a1, a2;
    for (int i = 0; i < K; ++i) {
        if (L[i] > 2) {
            int x = rando.next(N - L[i] + 1);
            int y = rando.next(N);
            if (rando.next(2)) {
                states.emplace_back(array<int, 5>{ x, y, L[i], 1, i });
            } else {
                states.emplace_back(array<int, 5>{ y, x, 1, L[i], i });
            }
            flip(states.back(), true);
        } else {
            (L[i] == 1 ? a1 : a2).emplace_back(i);
            score += L[i];
        }
    }
    for (int y = 0; y < N; ++y)
        score += N - (int)__builtin_popcountll(ls[y]);
    bestScore = score;
    bestStates = states;
    int ni = -1;
    vector<array<int, 3>> ne;
    for (int i = 0; i < (int)states.size(); ++i)
        for (int j = 0; j < 2; ++j)
            for (int k = 0; k < N; ++k)
                ne.emplace_back(array<int, 3>{ i, j, k });
    random_shuffle(ne.begin(), ne.end(), rando);
    bool hf = false;
    for (int iter = -1; ; ) {
        if ((++iter & 0x1fff) == 0) {
            double p = 1 - (timer.time() - timer.t) / timer.limit;
            if (p < 0) {
                //U(iter);
                break;
            } else if (!hf && p < 0.4) {
                hf = true;
                int n = (int)ne.size();
                for (int i = 0; i < n; ++i) {
                    auto& r = states[ne[i][0]];
                    for (int m = max(0, 5 - (r[2] != 1 ? r[2] : r[3])); m--; )
                        ne.emplace_back(ne[i]);
                }
                random_shuffle(ne.begin(), ne.end(), rando);
            }
            constexpr double InitialHeat = 0.8;
            constexpr double FinalHeat = 1e-9;
            double heat = p * (InitialHeat - FinalHeat) + FinalHeat;
            for (int i = 0; i < 128; ++i)
                ths[i] = log((i + 0.5) / 128) * heat;
            random_shuffle(ths, ths + 128, rando);
        }
        if (++ni == ne.size()) ni = 0;
        auto& r = states[ne[ni][0]];
        int l, diff;
        bool up = false;
        if (r[2] != 1) {
            l = r[2];
            unsigned long long mask = ((1ull << r[2]) - 1) << r[0];
            ls[r[1]] ^= mask;
            diff = l - (int)__builtin_popcountll(ls[r[1]] & mask) * 2;
            if (!ne[ni][1]) {
                mask = 1ull << r[1];
                for (int x = r[0]; x < r[0] + r[2]; ++x)
                    cs[x] ^= mask;
                up = true;
            }
        } else {
            l = r[3];
            unsigned long long mask = ((1ull << r[3]) - 1) << r[1];
            cs[r[0]] ^= mask;
            diff = l - (int)__builtin_popcountll(cs[r[0]] & mask) * 2;
            if (ne[ni][1]) {
                mask = 1ull << r[0];
                for (int y = r[1]; y < r[1] + r[3]; ++y)
                    ls[y] ^= mask;
                up = true;
            }
        }
        long long th = (long long)floor((ths[iter & 127] - diff + l) / 2);
        static vector<array<int, 5>> candidates;
        candidates.clear();
        if (ne[ni][1]) {
            int y = ne[ni][2];
            long long b = __builtin_popcountll(ls[y] & (1ull << l) - 1);
            unsigned long long l1 = ls[y];
            unsigned long long l2 = ls[y] >> l;
            for (int x = l; ; ++x) {
                if (b > th)
                    candidates.emplace_back(array<int, 5>{ x - l, y, l, 1, (int)b });
                if (x == N) break;
                b -= (l1 & 1) - (l2 & 1);
                l1 >>= 1;
                l2 >>= 1;
            }
        } else {
            int x = ne[ni][2];
            long long b = __builtin_popcountll(cs[x] & (1ull << l) - 1);
            unsigned long long c1 = cs[x];
            unsigned long long c2 = cs[x] >> l;
            for (int y = l; ; ++y) {
                if (b > th)
                    candidates.emplace_back(array<int, 5>{ x, y - l, 1, l, (int)b });
                if (y == N) break;
                b -= (c1 & 1) - (c2 & 1);
                c1 >>= 1;
                c2 >>= 1;
            }
        }
        if (candidates.empty()) {
            flip(r, up);
            continue;
        }
        auto& c = candidates.size() == 1 ? candidates[0] : candidates[rando.next((int)candidates.size())];        
        score += c[4] * 2 - l + diff;
        if (!up) {
            if (r[2] != 1) {
                unsigned long long mask = 1ull << r[1];
                for (int x = r[0]; x < r[0] + r[2]; ++x)
                    cs[x] ^= mask;
            } else {
                unsigned long long mask = 1ull << r[0];
                for (int y = r[1]; y < r[1] + r[3]; ++y)
                    ls[y] ^= mask;
            }
        }
        r[0] = c[0];
        r[1] = c[1];
        r[2] = c[2];
        r[3] = c[3];
        flip(r, true);
        if (bestScore < score) {
            bestScore = score;
            bestStates = states;
        }
    }
    score = bestScore;
    states.swap(bestStates);
    for (auto& r : states)
        for (int y = r[1]; y < r[1] + r[3]; ++y)
            for (int x = r[0]; x < r[0] + r[2]; ++x)
                A[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(array<int, 5>{ x, y - 1, 1, 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(array<int, 5>{ x - 1, y, 2, 1, a2.back() });
                a2.pop_back();
            }
        }
    }
    for (int y = 0; y < N; ++y) {
        for (int x = 0; x < N; ++x) {
            if (A[y][x] && a1.size()) {
                states.emplace_back(array<int, 5>{ x, y, 1, 1, a1.back() });
                a1.pop_back();
            }
        }
    }
    sort(states.begin(), states.end(), [](const array<int, 5>& a, const array<int, 5>& b) {
        return a[4] < b[4];
    });

    for (auto& r : states)
        cout << r[1] + 1 << ' ' << r[0] + 1 << ' ' << r[1] + r[3] << ' ' << r[0] + r[2] << endl;
    //cout << "# " << atoi(argv[1]) << ',' << score << endl;

    return 0;
}

yukicoder

結果

テストケース

ソースコード