結果

問題 No.5022 XOR Printer
コンテスト
ユーザー fepic_
提出日時 2026-06-17 13:51:12
言語 C++17
(gcc 15.2.0 + boost 1.89.0)
コンパイル:
g++-15 -O2 -lm -std=c++17 -Wuninitialized -DONLINE_JUDGE -o a.out _filename_
実行:
./a.out
結果
AC  
実行時間 3 ms / 2,000 ms
コード長 2,862 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 1,046 ms
コンパイル使用メモリ 114,912 KB
実行使用メモリ 6,400 KB
スコア 4,490,553,417
最終ジャッジ日時 2026-06-17 13:51:17
合計ジャッジ時間 3,970 ms
ジャッジサーバーID
（参考情報） 		judge1_1 / judge2_0
純コード判定しない問題か言語
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 50
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <cmath>

using namespace std;

int N, T;
vector<vector<long long>> A;
int curr_r = 0, curr_c = 0;
long long s = 0;
string ops = "";

void move_to(int tr, int tc) {
    while (curr_r < tr && ops.length() < T) { ops += "D"; curr_r++; }
    while (curr_r > tr && ops.length() < T) { ops += "U"; curr_r--; }
    while (curr_c < tc && ops.length() < T) { ops += "R"; curr_c++; }
    while (curr_c > tc && ops.length() < T) { ops += "L"; curr_c--; }
}

// ジグザグ順で次に進むべき座標を取得する関数
pair<int, int> get_next_zigzag(int r, int c) {
    // 現在の進む方向を判定（偶数行は右、奇数行は左）
    if (r % 2 == 0) {
        if (c + 1 < N) return {r, c + 1};
        else return {r + 1, c};
    } else {
        if (c - 1 >= 0) return {r, c - 1};
        else return {r + 1, c};
    }
}

int main() {
    if (!(cin >> N >> T)) return 0;
    A.assign(N, vector<long long>(N));
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) cin >> A[i][j];
    }

    for (int bit = 19; bit >= 0; --bit) {
        if (ops.length() >= T) break;

        // 1. sを更新する (C)
        bool s_updated = false;
        if (((s >> bit) & 1) == 0) {
            // 最も近い「対象ビットが1になるマス」を探して移動し、C
            int best_r = -1, best_c = -1;
            int min_dist = 10000;
            for (int i = 0; i < N; i++) {
                for (int j = 0; j < N; j++) {
                    if ((((s ^ A[i][j]) >> bit) & 1) == 1) {
                        int d = abs(curr_r - i) + abs(curr_c - j);
                        if (d < min_dist) { min_dist = d; best_r = i; best_c = j; }
                    }
                }
            }
            if (best_r != -1) {
                move_to(best_r, best_c);
                if (ops.length() < T) { ops += "C"; s ^= A[curr_r][curr_c]; s_updated = true; }
            }
        }

        // 2. pへ移動する
        // bitが奇数なら(0,0)、偶数なら(N-1,N-1)
        int pr = (bit % 2 != 0) ? 0 : N - 1;
        int pc = (bit % 2 != 0) ? 0 : N - 1;
        move_to(pr, pc);

        // 3. ジグザグに行動 (W)
        int r = curr_r, c = curr_c;
        while (ops.length() < T) {
            if (((A[r][c] >> bit) & 1) == 0) {
                if ((A[r][c] ^ s) > A[r][c]) {
                    // ここでW
                    ops += "W"; A[r][c] ^= s;
                }
            }
            // 次のマスへ
            if (r == N - 1 && ( (r%2==0 && c==N-1) || (r%2!=0 && c==0) )) break;
            pair<int, int> next = get_next_zigzag(r, c);
            move_to(next.first, next.second);
            r = curr_r; c = curr_c;
        }
    }

    for(char c : ops){
        cout << c << endl;
    }
    return 0;
}
0