結果

問題 No.5022 XOR Printer
ユーザー Sor4chi
提出日時 2025-07-26 13:26:41
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 1,952 ms / 2,000 ms
コード長 3,646 bytes
コンパイル時間 3,422 ms
コンパイル使用メモリ 296,840 KB
実行使用メモリ 7,716 KB
スコア 4,989,499,168
最終ジャッジ日時 2025-07-26 13:28:27
合計ジャッジ時間 105,315 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge5
純コード判定しない問題か言語
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 50
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

struct Action {
    int x, y;
    char op;
};

int N = 10;
constexpr double T0 = 1e3;
constexpr double T1 = 1e-3;
constexpr double TL = 1.95;
constexpr double INVALID_SCORE = -9999999;

int T;
vector<vector<int>> A0;
std::mt19937_64 rng(chrono::high_resolution_clock::now().time_since_epoch().count());

pair<ll, int> evaluate(const vector<Action>& seq) {
    vector<vector<int>> A = A0;
    int s = 0;
    int cx = 1, cy = 1;
    int turns = 0;
    for (auto& act : seq) {
        int tx = act.x, ty = act.y;
        int d = abs(cx - tx) + abs(cy - ty);
        turns += d + 1;
        if (turns > T) {
            return make_pair(INVALID_SCORE, T + 1);
        }
        if (act.op == 'C') {
            s ^= A[tx][ty];
        } else {
            A[tx][ty] ^= s;
        }
        cx = tx;
        cy = ty;
    }
    ll sum = 0;
    for (int i = 1; i <= N; i++)
        for (int j = 1; j <= N; j++)
            sum += A[i][j];
    return make_pair(sum, turns);
}

string buildOutput(const vector<Action>& seq) {
    string out;
    int cx = 1, cy = 1;
    for (auto& act : seq) {
        int dx = act.x - cx;
        int dy = act.y - cy;
        if (dx > 0)
            out += string(dx, 'D');
        else if (dx < 0)
            out += string(-dx, 'U');
        if (dy > 0)
            out += string(dy, 'R');
        else if (dy < 0)
            out += string(-dy, 'L');
        out.push_back(act.op);
        cx = act.x;
        cy = act.y;
    }
    return out;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    cin >> N >> T;
    A0.assign(N + 1, vector<int>(N + 1));
    for (int i = 1; i <= N; i++)
        for (int j = 1; j <= N; j++)
            cin >> A0[i][j];

    auto t0 = chrono::high_resolution_clock::now();

    vector<Action> best_seq, cur_seq;
    auto best_eval = evaluate(best_seq);
    auto cur_eval = best_eval;

    uniform_int_distribution<int> cell_dist(1, N);
    uniform_int_distribution<char> op_dist(0, 1);

    int iter = 0;

    while (true) {
        auto now = chrono::high_resolution_clock::now();
        double elapsed = chrono::duration<double>(now - t0).count();
        if (elapsed > TL) break;
        double temp = T0 * pow(T1 / T0, elapsed / TL);
        ++iter;
        vector<Action> nxt = cur_seq;
        int type = rng() % 3;
        if (type == 0) {
            // insert
            Action a{cell_dist(rng), cell_dist(rng), (op_dist(rng) ? 'C' : 'W')};
            int pos = nxt.empty() ? 0 : (rng() % (int)nxt.size());
            nxt.insert(nxt.begin() + pos, a);
        } else if (type == 1 && !nxt.empty()) {
            // delete
            int pos = rng() % (int)nxt.size();
            nxt.erase(nxt.begin() + pos);
        } else if (type == 2 && nxt.size() >= 2) {
            // swap two
            int i = rng() % nxt.size();
            int j = rng() % nxt.size();
            swap(nxt[i], nxt[j]);
        }

        auto nxt_eval = evaluate(nxt);
        ll dE = nxt_eval.first - cur_eval.first;
        if (dE > 0 || exp(dE / temp) > (double)(rng() & 0xFFFFFFFFULL) / (double)0xFFFFFFFFULL) {
            cur_seq = move(nxt);
            cur_eval = nxt_eval;
            if (cur_eval.first > best_eval.first) {
                best_seq = cur_seq;
                best_eval = cur_eval;
            }
        }
    }

    cerr << "iter = " << iter << endl;
    cerr << "best.score = " << best_eval.first << endl;

    string ops = buildOutput(best_seq);
    if ((int)ops.size() > T) ops = ops.substr(0, T);
    for (char c : ops) {
        cout << c << "\n";
    }
    return 0;
}
0