結果

問題 No.5022 XOR Printer
コンテスト
ユーザー bird01
提出日時 2025-07-26 13:45:35
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 3 ms / 2,000 ms
コード長 3,341 bytes
コンパイル時間 3,708 ms
コンパイル使用メモリ 285,388 KB
実行使用メモリ 7,720 KB
スコア 3,928,291,492
最終ジャッジ日時 2025-07-26 13:45:42
合計ジャッジ時間 6,009 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge2
純コード判定しない問題か言語
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 50
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

// 1.ベースライン,何もしない
// 2.最適なsを求め,全セルをフリップ→?
// 3.最大桁を1にする

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

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

    const int N = 10;           // 問題の定数
    const int T = 1000;         // 最大操作回数（今回は気にせず）

    // 入力
    int n, t;
    cin >> n >> t;
    vector<vector<int>> A(n+1, vector<int>(n+1));
    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= n; ++j)
            cin >> A[i][j];

    vector<char> ops;
    int cx = 1, cy = 1;  // 現在位置

    // --- 1) 対象ビットを決定 ---
    // グリッド中で1が立っている最上位ビットを探す
    int target_bit = -1;
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= n; ++j) {
            if (A[i][j] > 0) {
                int b = 31 - __builtin_clz(A[i][j]);
                target_bit = max(target_bit, b);
            }
        }
    }
    // もしそのビットがどこにも立っていなければ、一つ下のビットを試す
    while (target_bit >= 0) {
        bool found = false;
        for (int i = 1; i <= n; ++i) {
            for (int j = 1; j <= n; ++j) {
                if ((A[i][j] >> target_bit) & 1) {
                    found = true;
                    break;
                }
            }
            if (found) break;
        }
        if (found) break;
        --target_bit;
    }
    if (target_bit < 0) {
        // 何もできないなら終了
        for (char c : ops) cout << c << "\n";
        return 0;
    }

    // --- ヘルパー: (cx,cy) から (tx,ty) へ移動 ---
    auto moveTo = [&](int tx, int ty) {
        while (cx < tx) { ops.push_back('D'); ++cx; }
        while (cx > tx) { ops.push_back('U'); --cx; }
        while (cy < ty) { ops.push_back('R'); ++cy; }
        while (cy > ty) { ops.push_back('L'); --cy; }
    };

    // --- 2) 現在位置から一番近い「target_bit が 1 のセル」へ移動し、コピー(C) ---
    int best_i = -1, best_j = -1, best_dist = INT_MAX;
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= n; ++j) {
            if ((A[i][j] >> target_bit) & 1) {
                int d = abs(i - cx) + abs(j - cy);
                if (d < best_dist) {
                    best_dist = d;
                    best_i = i;
                    best_j = j;
                }
            }
        }
    }
    // 移動してコピー
    moveTo(best_i, best_j);
    ops.push_back('C');

    // --- 3) (1,1) に戻ってから蛇行走査 ---
    moveTo(1, 1);

    for (int i = 1; i <= n; ++i) {
        if (i % 2 == 1) {
            // 左→右
            for (int j = 1; j <= n; ++j) {
                moveTo(i, j);
                // まだ target_bit が 0 のセルなら書き込み(W)
                if (!((A[i][j] >> target_bit) & 1)) {
                    ops.push_back('W');
                }
            }
        } else {
            // 右→左
            for (int j = n; j >= 1; --j) {
                moveTo(i, j);
                if (!((A[i][j] >> target_bit) & 1)) {
                    ops.push_back('W');
                }
            }
        }
    }

    // --- 出力 ---
    for (char c : ops) {
        cout << c << "\n";
    }
    return 0;
}
0