結果

問題 No.5022 XOR Printer
ユーザー Ang1077
提出日時 2025-07-26 13:57:37
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 4 ms / 2,000 ms
コード長 5,064 bytes
コンパイル時間 2,955 ms
コンパイル使用メモリ 287,924 KB
実行使用メモリ 7,716 KB
スコア 4,827,535,319
最終ジャッジ日時 2025-07-26 13:57:44
合計ジャッジ時間 5,193 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge2
純コード判定しない問題か言語
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 50
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In function ‘int main()’:
main.cpp:156:17: warning: ‘sum’ may be used uninitialized [-Wmaybe-uninitialized]
  156 |             sum += A[i][j];
main.cpp:152:14: note: ‘sum’ was declared here
  152 |     uint32_t sum;
      |              ^~~

ソースコード

diff # 

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

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

    int N, T;
    if (!(cin >> N >> T))
        return 0;
    vector<vector<uint32_t>> A(N, vector<uint32_t>(N));
    for (int i = 0; i < N; ++i)
        for (int j = 0; j < N; ++j)
            cin >> A[i][j];

    // 状態
    int r = 0, c = 0; // 現在位置 (0-indexed)
    uint32_t s = 0;   // 手持ち
    vector<char> ops; // 出力操作列

    // 一度でもWしたかの管理
    vector<uint8_t> written(N * N, 0);
    int written_cnt = 0;

    auto idx = [&](int rr, int cc) { return rr * N + cc; };

    auto move_to = [&](int tr, int tc) {
        while (r < tr) {
            ops.push_back('D');
            ++r;
        }
        while (r > tr) {
            ops.push_back('U');
            --r;
        }
        while (c < tc) {
            ops.push_back('R');
            ++c;
        }
        while (c > tc) {
            ops.push_back('L');
            --c;
        }
    };
    auto manhattan = [&](int r1, int c1, int r2, int c2) {
        return abs(r1 - r2) + abs(c1 - c2);
    };

    int used = 0;
    while (used < T) {
        int rem = T - used;
        if (rem < 1)
            break;

        // 動的コスト上限： (残り手数 / 未書込マス数) * 1.25
        int remaining_unwritten = max(0, N * N - written_cnt);
        int denom = max(1, remaining_unwritten); // 0除算回避
        double budget_d = (double)rem / (double)denom * 2;
        int K = min(rem, (int)floor(budget_d));
        if (K < 1)
            break;

        long long best_delta = 0; // 改善のみ採用
        int best_cost = 0;

        // mode: 0=コピー0回, 1=コピー1回
        int mode = -1;
        int bwr = -1, bwc = -1; // 書き込み先
        int bpr = -1, bpc = -1; // 1回コピーのコピー元

        // --- コピー0回: 現在位置 -> W ---
        for (int wr = 0; wr < N; ++wr) {
            for (int wc = 0; wc < N; ++wc) {
                int total_cost = manhattan(r, c, wr, wc) + 1; // move + W
                if (total_cost > K)
                    continue;
                uint32_t new_val = (A[wr][wc] ^ s);
                long long delta = (long long)new_val - (long long)A[wr][wc];
                if (delta > best_delta || (delta == best_delta && delta > 0 &&
                                           total_cost < best_cost)) {
                    best_delta = delta;
                    best_cost = total_cost;
                    mode = 0;
                    bwr = wr;
                    bwc = wc;
                }
            }
        }

        // --- コピー1回: 現在位置 -> C -> W ---
        for (int pr = 0; pr < N; ++pr) {
            for (int pc = 0; pc < N; ++pc) {
                int cost_to_p = manhattan(r, c, pr, pc);
                // これ以降に C(1) + 移動 + W(1)
                if (cost_to_p + 2 > K)
                    continue;
                uint32_t s2 = s ^ A[pr][pc];
                for (int wr = 0; wr < N; ++wr) {
                    for (int wc = 0; wc < N; ++wc) {
                        int total_cost =
                            cost_to_p + 1 + manhattan(pr, pc, wr, wc) + 1;
                        if (total_cost > K)
                            continue;
                        uint32_t new_val = (A[wr][wc] ^ s2);
                        long long delta =
                            (long long)new_val - (long long)A[wr][wc];
                        if (delta > best_delta ||
                            (delta == best_delta && delta > 0 &&
                             total_cost < best_cost)) {
                            best_delta = delta;
                            best_cost = total_cost;
                            mode = 1;
                            bpr = pr;
                            bpc = pc;
                            bwr = wr;
                            bwc = wc;
                        }
                    }
                }
            }
        }

        // 改善なしなら終了
        if (best_delta <= 0 || mode < 0)
            break;

        // 実行
        if (mode == 0) {
            move_to(bwr, bwc);
            ops.push_back('W');
            A[bwr][bwc] ^= s;
        } else { // mode == 1
            move_to(bpr, bpc);
            ops.push_back('C');
            s ^= A[bpr][bpc];
            move_to(bwr, bwc);
            ops.push_back('W');
            A[bwr][bwc] ^= s;
        }

        // 一度も書き込んでいなかったマスならフラグ更新
        int id = idx(bwr, bwc);
        if (!written[id]) {
            written[id] = 1;
            ++written_cnt;
        }

        used += best_cost;
    }

    cerr << ops.size() << '\n';
    uint32_t sum;
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            cerr << A[i][j] << " ";
            sum += A[i][j];
        }
        cerr << '\n';
    }
    cerr << sum << '\n';
    // 出力
    for (char ch : ops)
        cout << ch << '\n';
    return 0;
}
0