結果

問題 No.5002 stick xor
ユーザー hakomohakomo
提出日時 2018-05-26 13:29:21
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 955 ms / 1,000 ms
コード長 5,915 bytes
コンパイル時間 33,702 ms
実行使用メモリ 2,380 KB
スコア 46,323
最終ジャッジ日時 2018-05-26 13:29:56
ジャッジサーバーID
（参考情報） 		judge6 /
純コード判定しない問題か言語
このコードへのチャレンジ
（要ログイン）

テストケース

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

ソースコード

diff # 

#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.95;
    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];
vector<array<int, 5>> states, bestStates;
int score, bestScore;
double ths[128];

inline void flip(const array<int, 5>& r) {
    if (r[2] != 1) {
        for (int x = r[0]; x < r[0] + r[2]; ++x)
            A[r[1]][x] ^= 1;
    } else {
        for (int y = r[1]; y < r[1] + r[3]; ++y)
            A[y][r[0]] ^= 1;
    }
}

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[61];
        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 i = 0; i < K; ++i) {
        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());
    }
    score = bestScore = 0;
    bestStates = states;
    int ni = -1;
    vector<array<int, 3>> ne;
    for (int i = 0; i < K; ++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);
    for (int iter = -1; ; ) {
        if ((++iter & 0xfff) == 0) {
            double p = 1 - (timer.time() - timer.t) / timer.limit;
            if (p < 0) {
                //U(iter);
                break;
            }
            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 = 0;
        if (r[2] != 1) {
            l = r[2];
            for (int x = r[0]; x < r[0] + r[2]; ++x)
                diff += (A[r[1]][x] ^= 1) ? -1 : 1;
        } else {
            l = r[3];
            for (int y = r[1]; y < r[1] + r[3]; ++y)
                diff += (A[y][r[0]] ^= 1) ? -1 : 1;
        }
        int th = (int)floor((ths[iter & 127] - diff + l) / 2);
        static vector<array<int, 5>> candidates;
        candidates.clear();
        if (ne[ni][1]) {
            int y = ne[ni][2];
            int b = 0;
            for (int x = 0; x < l; ++x)
                b += A[y][x];
            for (int x = 0; ; ++x) {
                if (b > th)
                    candidates.emplace_back(array<int, 5>{ x, y, l, 1, b * 2 - l + diff });
                if (x + l == N) break;
                b -= A[y][x] - A[y][x + l];
            }
        } else {
            int x = ne[ni][2];
            int b = 0;
            for (int y = 0; y < l; ++y)
                b += A[y][x];
            for (int y = 0; ; ++y) {
                if (b > th)
                    candidates.emplace_back(array<int, 5>{ x, y, 1, l, b * 2 - l + diff });
                if (y + l == N) break;
                b -= A[y][x] - A[y + l][x];
            }
        }
        if (candidates.empty()) {
            flip(r);
            continue;
        }
        auto& c = candidates.size() == 1 ? candidates[0] : candidates[rando.next((int)candidates.size())];
        score += c[4];
        r[0] = c[0];
        r[1] = c[1];
        r[2] = c[2];
        r[3] = c[3];
        flip(r);
        if (bestScore < score) {
            bestScore = score;
            bestStates = states;
        }
    }
    score = bestScore;
    states.swap(bestStates);
    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;
}
0