#1108077 (C++17) No.5022 XOR Printer

• 問題: No.5022 XOR Printer
• ユーザー: tabae326
• 提出日時: 2025-07-26 16:39:08
• 言語: C++17 (gcc 13.3.0 + boost 1.87.0)
• 結果: AC
• 実行時間: 1,804 ms / 2,000 ms
• コード長: 10,841 bytes
• コンパイル時間: 1,499 ms
• コンパイル使用メモリ: 120,064 KB
• 実行使用メモリ: 7,716 KB
• スコア: 4,678,896,294
• 最終ジャッジ日時: 2025-07-26 16:40:45
• 合計ジャッジ時間: 95,187 ms
• ジャッジサーバーID （参考情報）: judge4 / judge5

ファイルパターン	結果
other	AC * 50

ソースコード

#include <iostream>
#include <bitset>

#ifndef __ANNEALER_HPP__
#define __ANNEALER_HPP__

#ifndef __RYUKA_HPP__
#define __RYUKA_HPP__

#include <random>
using namespace std;

struct RandGenerator {
    random_device seed_gen;
    mt19937 engine;
    mt19937_64 engine64;
    static const int pshift = 1000000000;

    RandGenerator() : engine(seed_gen()), engine64(seed_gen()) {}

    int rand(int mod) { return engine() % mod; }

    long long randll(long long mod) { return engine64() % mod; }

    bool pjudge(double p) {
        int p_int;
        if (p > 1)
            p_int = pshift;
        else
            p_int = p * pshift;
        return rand(pshift) < p_int;
    }

} ryuka;

#endif
#ifndef __TOKI_HPP__
#define __TOKI_HPP__

#include <sys/time.h>

#include <cstddef>

struct Timer {
    double global_start;

    double gettime() {
        struct timeval tv;
        gettimeofday(&tv, NULL);
        return tv.tv_sec + tv.tv_usec * 1e-6;
    }

    void init() { global_start = gettime(); }

    double elapsed() { return gettime() - global_start; }
} toki;

#endif

extern Timer toki;
extern RandGenerator ryuka;

template <class STATE>
struct IterationControl {
    long long iteration_counter;
    long long swap_counter;
    double average_time;
    double start_time;
    bool liner_cooling;
    bool save_best_answer;
    bool use_rollback;
    bool maximize;
    int gettime_interval;
    IterationControl()
        : iteration_counter(0),
          swap_counter(0),
          liner_cooling(false),
          save_best_answer(true),
          use_rollback(false),
          maximize(true),
          gettime_interval(1) {}
    STATE climb(double time_limit, STATE initial_state);
    STATE anneal(double time_limit, double temp_start, double temp_end,
                 STATE initial_state);
};

template <class STATE>
STATE IterationControl<STATE>::climb(double time_limit, STATE initial_state) {
    start_time = toki.gettime();
    average_time = 0;
    STATE best_state = initial_state;
    double time_stamp = start_time;
    cerr << "Start climbing...\n";
    while (time_stamp - start_time + average_time < time_limit) {
        if (use_rollback) {
            long long best_score = best_state.score;
            best_state.nextState();
            long long delta = best_state.score - best_score;
            if (!maximize) {
                delta = -delta;
            }
            if (delta > 0) {
                swap_counter++;
            } else {
                best_state.rollback();
                best_state.score = best_score;
            }
        } else {
            STATE current_state = STATE::generateState(best_state);
            long long delta = current_state.score - best_state.score;
            if (!maximize) {
                delta = -delta;
            }
            if (delta > 0) {
                swap(best_state, current_state);
                swap_counter++;
            }
        }
        iteration_counter++;
        if (iteration_counter % gettime_interval == 0) {
            time_stamp = toki.gettime();
            average_time = (time_stamp - start_time) / iteration_counter;
        }
    }
    cerr << "Iterated " << iteration_counter << " times and swapped "
         << swap_counter << " times.\n";
    return best_state;
}

template <class STATE>
STATE IterationControl<STATE>::anneal(double time_limit, double temp_start,
                                      double temp_end, STATE initial_state) {
    start_time = toki.gettime();
    average_time = 0;
    STATE current_state = initial_state;
    STATE answer_state = initial_state;
    double elapsed_time = 0;
    const double inv_time_limit = 1.0 / time_limit;
    cerr << "Start annealing...\n";
    while (elapsed_time + average_time < time_limit) {
        double temp_current;
        if (liner_cooling) {
            const double normalized_time = elapsed_time * inv_time_limit;
            temp_current =
                temp_start + (temp_end - temp_start) * normalized_time;
        } else {
            const double normalized_time = elapsed_time * inv_time_limit;
            temp_current = pow(temp_start, 1.0 - normalized_time) *
                           pow(temp_end, normalized_time);
        }

        if (use_rollback) {
            long long prev_score = current_state.score;
            current_state.nextState();
            long long delta = current_state.score - prev_score;
            long long delta_ans = current_state.score - answer_state.score;
            if (!maximize) {
                delta = -delta;
                delta_ans = -delta_ans;
            }
            if (save_best_answer && delta_ans > 0) {
                answer_state = current_state;
            }
            if (delta > 0 || ryuka.pjudge(exp(1.0 * delta / temp_current))) {
                swap_counter++;
            } else {
                current_state.rollback();
                current_state.score = prev_score;
            }
        } else {
            STATE new_state = STATE::generateState(current_state);
            long long delta = new_state.score - current_state.score;
            long long delta_ans = new_state.score - answer_state.score;
            if (!maximize) {
                delta = -delta;
                delta_ans = -delta_ans;
            }
            if (save_best_answer && delta_ans > 0) {
                answer_state = new_state;
            }
            if (delta > 0 || ryuka.pjudge(exp(1.0 * delta / temp_current))) {
                swap(new_state, current_state);
                swap_counter++;
            }
        }

        iteration_counter++;
        if (iteration_counter % gettime_interval == 0) {
            elapsed_time = toki.gettime() - start_time;
            average_time = elapsed_time / iteration_counter;
        }
    }
    cerr << "Iterated " << iteration_counter << " times and swapped "
         << swap_counter << " times.\n";
    return save_best_answer ? answer_state : current_state;
}

#endif

#include <cmath>
#include <iostream>
#include <vector>
using namespace std;
using ll = long long;

namespace common {
    constexpr int n = 10;
    constexpr int t = 1000;
    int a[n][n];
    void read();
    void copy_a(int src[n][n], int dst[n][n]) {
        for(int i = 0; i < n; i++) {
            for(int j = 0; j < n; j++) {
                dst[i][j] = src[i][j];
            }
        }
    }
    bool is_in_field(int i, int j) {
        return i >= 0 && i < n && j >= 0 && j < n;
    }
};  // namespace common

void common::read() {
    int _n, _t;
    cin >> _n >> _t;
    for(int i = 0; i < n; i++) {
        for(int j = 0; j < n; j++) {
            cin >> a[i][j];
        }
    }
}

#include <algorithm>
#include <cassert>
#include <numeric>


using namespace std;
using namespace common;

extern RandGenerator ryuka;

struct Operation {
    char type;
    pair<int, int> dir() const {
        if(type == 'U') return {-1, 0};
        if(type == 'D') return {1, 0};
        if(type == 'L') return {0, -1};
        if(type == 'R') return {0, 1};
        assert(false && "Invalid operation type");
    }
    Operation(char t) : type(t) {}
    Operation() = default;
};

struct State {
    static constexpr long long inf = 1LL << 60;
    static constexpr int num_c = 6;
    long long score;
    int a[n][n];
    vector<pair<int,int>> c_pos;
    vector<Operation> ops;
    State() : score(-inf) { ; };
    long long calc_score();
    void apply(char, int&, int&, int&);
    pair<int, int> move_to(int, int, int, int);
    void fill_ops();
    void print();
    void rollback();
    void nextState();
    static State initState();
    static State generateState(const State& input_state);
};

long long State::calc_score() {
    score = 0;
    for(int i = 0; i < n; i++) {
        for(int j = 0; j < n; j++) {
            score += this->a[i][j];
        }
    }
    return score;
}

void State::print() {
    for(const Operation& op: ops) {
        cout << op.type << endl;
    }
}

void State::apply(char type, int& i, int& j, int& s) {
    if(type == 'U') {
        i--;
    } else if(type == 'D') {
        i++;
    } else if(type == 'L') {
        j--;
    } else if(type == 'R') {
        j++;
    } else if(type == 'C') {
        s ^= this->a[i][j];
    } else if(type == 'W') {
        this->a[i][j] ^= s;
    } else {
        cerr << "Invalid operation type: " << type << endl;
        assert(false);
    }
    ops.push_back(Operation(type));
}

pair<int, int> State::move_to(int si, int sj, int di, int dj) {
    if(si == di && sj == dj) return {di, dj};
    for(int i = si; i < di; i++) ops.push_back(Operation('D'));
    for(int i = si; i > di; i--) ops.push_back(Operation('U'));
    for(int j = sj; j < dj; j++) ops.push_back(Operation('R'));
    for(int j = sj; j > dj; j--) ops.push_back(Operation('L'));
    return {di, dj};
}

void State::fill_ops() {
    int i = 0, j = 0, s = 0;
    ops.clear();
    copy_a(common::a, this->a);
    for(auto [ni, nj]: c_pos) {
        tie(i, j) = move_to(i, j, ni, nj);
        apply('C', i, j, s);
        tie(i, j) = move_to(i, j, 0, 0);
        while(true) {
            if((s ^ this->a[i][j]) > this->a[i][j]) apply('W', i, j, s);
            if(i == n-1 && j == 0) break;
            if(i % 2 == 0) {
                if(j != n-1) apply('R', i, j, s);
                else apply('D', i, j, s);
            } else {
                if(j != 0) apply('L', i, j, s);
                else apply('D', i, j, s);
            }
        }
    }
    while(ops.size() > t) {
        ops.pop_back();
    }
}

State State::initState() {
    State res;
    for(int i = 0; i < num_c; i++) {
        int x = ryuka.rand(n);
        int y = ryuka.rand(n);
        res.c_pos.emplace_back(x, y);
    }
    res.fill_ops();
    res.calc_score();
    return res;
}

State State::generateState(const State& input_state) {
    State res = input_state;
    if(ryuka.pjudge(0.5)) {
        int i = ryuka.rand(num_c);
        int j = ryuka.rand(num_c);
        swap(res.c_pos[i], res.c_pos[j]);
    } else {
        int i = ryuka.rand(n);
        int j = ryuka.rand(n);
        int p = ryuka.rand(num_c);
        res.c_pos[p] = {i, j};
    }
    res.fill_ops();
    res.calc_score();
    return res;
}

void State::nextState() {
}

void State::rollback() {
}
using namespace std;
using namespace common;

extern Timer toki;

int main() {
    toki.init();
    read();

    IterationControl<State> sera;
    //State stat = State::initState();
    State stat = sera.anneal(1.8, 1e6, 1e-2, State::initState());
    stat.print();
    
    for(int i = 0; i < n; i++) {
        for(int j = 0; j < n; j++) {
            cerr << bitset<20>(stat.a[i][j]) << " ";
        }
        cerr << endl;
    }

    cerr << "my score = " << stat.score << endl;
    cerr << "elapsed time = " << toki.elapsed() << endl;
}