結果

問題 No.5022 XOR Printer
コンテスト
ユーザー shim0
提出日時 2025-07-26 15:55:34
言語 Rust
(1.83.0 + proconio)
結果
AC  
実行時間 3 ms / 2,000 ms
コード長 5,083 bytes
コンパイル時間 11,916 ms
コンパイル使用メモリ 401,936 KB
実行使用メモリ 7,716 KB
スコア 5,169,544,629
最終ジャッジ日時 2025-07-26 15:55:50
合計ジャッジ時間 14,612 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge6
純コード判定しない問題か言語
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 50
権限があれば一括ダウンロードができます

ソースコード

diff # 

use proconio::input;

struct Input {
    n: usize,
    t: usize,
    a: Vec<Vec<u32>>,
}

fn read_input() -> Input {
    input! {
        n: usize,
        t: usize,
        a: [[u32; n]; n],
    }
    Input { n, t, a }
}

fn move_to(output: &mut Vec<char>, now_i: &mut usize, now_j: &mut usize, t_i: usize, t_j: usize) {
    while *now_i > t_i {
        output.push('U');
        *now_i -= 1;
    }
    while *now_i < t_i {
        output.push('D');
        *now_i += 1;
    }
    while *now_j > t_j {
        output.push('L');
        *now_j -= 1;
    }
    while *now_j < t_j {
        output.push('R');
        *now_j += 1;
    }
}

fn solver(input: &Input) -> Vec<char> {
    let mut output = vec![];
    let mut now_i = 0;
    let mut now_j = 0;
    let mut s: u32 = 0;
    let mut a = input.a.clone();

    for bit in (0..20).rev() {
        // for bit in (17..20).rev() {
        if output.len() >= input.t {
            break;
        }

        // phase 1 ターゲットの bit も含む左で全部 1
        if (s & (((1 << 30) - 1) << bit)) == (((1 << 30) - 1) << bit) & ((1 << 20) - 1) {
            {}
        } else {
            let mut target_i = usize::MAX;
            let mut target_j = usize::MAX;
            let mut target_distance = isize::MAX;
            for i in 0..input.n {
                for j in 0..input.n {
                    let is_ok = (a[i][j] & (((1 << 30) - 1) << bit)) == (((1 << 30) - 1) << bit) & ((1 << 20) - 1);
                    if !is_ok {
                        continue;
                    }
                    let distance = (now_i as isize - i as isize).abs() + (now_j as isize - j as isize).abs();
                    if distance < target_distance {
                        target_distance = distance;
                        target_i = i;
                        target_j = j;
                    }
                }
            }

            if target_i == usize::MAX || target_j == usize::MAX {
                eprintln!("something is wrong");
                break;
            }

            move_to(&mut output, &mut now_i, &mut now_j, target_i, target_j);
            output.push('W');
            output.push('C');
            a[target_i][target_j] ^= s;
            s ^= a[target_i][target_j];
        }
        eprintln!("bit: {}", bit);
        eprintln!("s: {:020b}", s);

        // phase 2 ターゲットより左を全部 0 にする
        if (s & (((1 << 30) - 1) << (bit + 1))) == 0 {
            {}
        } else {
            let mut target_i = usize::MAX;
            let mut target_j = usize::MAX;
            let mut target_distance = isize::MAX;
            for i in 0..input.n {
                for j in 0..input.n {
                    let mut is_ok = (a[i][j] & (((1 << 30) - 1) << (bit + 1))) == (((1 << 30) - 1) << (bit + 1)) & ((1 << 20) - 1);
                    is_ok &= (a[i][j] & (1 << bit)) == 0;
                    if !is_ok {
                        continue;
                    }
                    let distance = (now_i as isize - i as isize).abs() + (now_j as isize - j as isize).abs();
                    if distance < target_distance {
                        target_distance = distance;
                        target_i = i;
                        target_j = j;
                    }
                }
            }
            if target_i == usize::MAX || target_j == usize::MAX {
                eprintln!("something is wrong");
                break;
            }
            move_to(&mut output, &mut now_i, &mut now_j, target_i, target_j);
            output.push('C');
            s ^= a[target_i][target_j];
        }
        eprintln!("s: {:020b}", s);
        eprintln!("s: {}", s);

        for i in 0..input.n {
            if i % 2 == 0 {
                for j in 0..input.n {
                    if a[i][j] <= a[i][j] ^ s {
                        move_to(&mut output, &mut now_i, &mut now_j, i, j);
                        a[i][j] ^= s;
                        output.push('W');
                    }
                }
            } else {
                for j in (0..input.n).rev() {
                    if a[i][j] <= a[i][j] ^ s {
                        move_to(&mut output, &mut now_i, &mut now_j, i, j);
                        a[i][j] ^= s;
                        output.push('W');
                    }
                }
            }
        }
        eprintln!("bit: {}", bit);
        for i in 0..input.n {
            eprintln!("{}", a[i].iter().map(|v| format!("{:020b}", v)).collect::<Vec<String>>().join(" "));
        }

        for i in 0..input.n {
            eprintln!("{}", a[i].iter().map(|v| v.to_string()).collect::<Vec<String>>().join(" "));
        }
        let mut score = 0;
        for i in 0..input.n {
            for j in 0..input.n {
                score += a[i][j];
            }
        }
        eprintln!("score: {}", score);
    }

    output.truncate(input.t);
    output
}

fn main() {
    let input = read_input();

    let output = solver(&input);
    for c in output.iter() {
        println!("{}", c);
    }
}
0