結果

問題 No.5022 XOR Printer
ユーザー ロロット
提出日時 2025-07-26 16:47:29
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 3,941 bytes
コンパイル時間 3,139 ms
コンパイル使用メモリ 289,716 KB
実行使用メモリ 7,720 KB
スコア 0
最終ジャッジ日時 2025-07-26 16:47:43
合計ジャッジ時間 4,844 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other WA * 50
権限があれば一括ダウンロードができます

ソースコード

diff # 

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

// セル情報
struct Cell {
    int r, c;
    uint32_t v;
    bool updated = false;
};

int N, T;
vector<vector<Cell>> grid;
vector<char> ops;
int curR = 1, curC = 1;
uint32_t s = 0;

// 操作を記録
inline void applyOp(char c) {
    ops.push_back(c);
}

// カーソル移動
void moveTo(int tr, int tc) {
    while (curR < tr) { applyOp('D'); ++curR; }
    while (curR > tr) { applyOp('U'); --curR; }
    while (curC < tc) { applyOp('R'); ++curC; }
    while (curC > tc) { applyOp('L'); --curC; }
}

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

    cin >> N >> T;
    grid.assign(N+1, vector<Cell>(N+1));
    for (int i = 1; i <= N; ++i) {
        for (int j = 1; j <= N; ++j) {
            cin >> grid[i][j].v;
            grid[i][j].r = i;
            grid[i][j].c = j;
        }
    }
    ops.reserve(T);

    // フェーズ1: 最大値セルをコピーして s を初期化
    int mr = 1, mc = 1;
    uint32_t maxV = grid[1][1].v;
    for (int i = 1; i <= N; ++i) {
        for (int j = 1; j <= N; ++j) {
            if (grid[i][j].v > maxV) {
                maxV = grid[i][j].v;
                mr = i; mc = j;
            }
        }
    }
    moveTo(mr, mc);
    applyOp('C');
    s ^= grid[mr][mc].v;

    // フェーズ2: s を使って全セル単騎 W 改善
    for (int i = 1; i <= N && (int)ops.size() < T; ++i) {
        for (int j = 1; j <= N && (int)ops.size() < T; ++j) {
            uint32_t oldv = grid[i][j].v;
            uint32_t newv = oldv ^ s;
            if (newv > oldv) {
                moveTo(i, j);
                applyOp('W');
                grid[i][j].v = newv;
            }
        }
    }

    // フェーズ3: 全探索ペア改善
    const int PAIR_COST_EST = 40;
    // フラグリセット
    for (int i = 1; i <= N; ++i)
        for (int j = 1; j <= N; ++j)
            grid[i][j].updated = false;

    while ((int)ops.size() + PAIR_COST_EST < T) {
        int ar=-1, ac=-1, br=-1, bc=-1;
        int64_t bestGain = 0;

        // 全ペア探索
        for (int i = 1; i <= N; ++i) {
            for (int j = 1; j <= N; ++j) {
                if (grid[i][j].updated) continue;
                uint32_t A = grid[i][j].v;
                for (int p = 1; p <= N; ++p) {
                    for (int q = 1; q <= N; ++q) {
                        if ((i==p && j==q) || grid[p][q].updated) continue;
                        uint32_t B = grid[p][q].v;
                        uint32_t x = A ^ B;
                        int64_t gain = 2LL * x - A - B;
                        if (gain > bestGain) {
                            bestGain = gain;
                            ar = i; ac = j;
                            br = p; bc = q;
                        }
                    }
                }
            }
        }
        if (bestGain <= 0) break;

        // ペア改善操作 (C/W/C/W)
        moveTo(ar, ac);
        applyOp('C');  s ^= grid[ar][ac].v;

        moveTo(br, bc);
        applyOp('W');  grid[br][bc].v ^= s;

        applyOp('C');  s ^= grid[br][bc].v;

        moveTo(ar, ac);
        applyOp('W');  grid[ar][ac].v ^= s;

        grid[ar][ac].updated = grid[br][bc].updated = true;
    }

    // フェーズ4: 終端へ移動して C し、s を更新
    moveTo(N, N);
    applyOp('C');
    s ^= grid[N][N].v;

    // フェーズ5: 逆順 (N→1, N→1) に W 更新可能なセルを消化
    for (int i = N; i >= 1 && (int)ops.size() < T; --i) {
        for (int j = N; j >= 1 && (int)ops.size() < T; --j) {
            uint32_t oldv = grid[i][j].v;
            uint32_t newv = oldv ^ s;
            if (newv > oldv) {
                moveTo(i, j);
                applyOp('W');
                grid[i][j].v = newv;
            }
        }
    }

    // 出力
    for (int i = 0, M = ops.size(); i < M; ++i) {
        cout << ops[i] << (i+1 < M ? ' ' : '\n');
    }
    return 0;
}
0