#1108003 (Rust) No.5022 XOR Printer

提出ソース
結果

問題	No.5022 XOR Printer
ユーザー	tomerun
提出日時	2025-07-26 15:59:32
言語	Rust (1.83.0 + proconio)
結果	AC
実行時間	1,947 ms / 2,000 ms
コード長	16,330 bytes
コンパイル時間	11,692 ms
コンパイル使用メモリ	399,720 KB
実行使用メモリ	7,716 KB
スコア	5,201,061,106
最終ジャッジ日時	2025-07-26 16:01:43
合計ジャッジ時間	110,957 ms
ジャッジサーバーID （参考情報）	judge5 / judge2
	純コード判定しない問題か言語
このコードへのチャレンジ
（要ログイン）
ファイルパターン	結果
other	AC * 50
権限があれば一括ダウンロードができます
ソースコード

raw source code
#![allow(unused_imports)]
#![allow(dead_code)]
#![allow(non_snake_case)]
use std::env;
use std::io::{self, BufRead, BufReader, Read, Stdin};
use std::iter;
use std::mem;
use std::str::FromStr;
use std::string::String;
use std::time;

const TIMELIMIT: u64 = 1850;
const INF: usize = 1 << 28;
const N: usize = 10;
const T: usize = 1000;
const DY: [usize; 4] = [!0, 0, 1, 0];
const DX: [usize; 4] = [0, 1, 0, !0];
const DIR_UP: usize = 0;
const DIR_RIGHT: usize = 1;
const DIR_DOWN: usize = 2;
const DIR_LEFT: usize = 3;

#[derive(Debug)]
pub struct Scanner<R> {
    reader: BufReader<R>,
}

fn scanner() -> Scanner<Stdin> {
    Scanner::new(io::stdin())
}

impl<R: io::Read> Scanner<R> {
    pub fn new(read: R) -> Scanner<R> {
        Scanner {
            reader: BufReader::new(read),
        }
    }

    pub fn next_str(&mut self) -> Option<String> {
        let mut buf = [0; 1];
        let size = self.reader.read(&mut buf).unwrap();
        if size == 0 {
            None
        } else {
            self.skip_whitespace(&mut buf)?;
            let mut v = vec![buf[0]];
            loop {
                let size = self.reader.read(&mut buf).unwrap();
                if size == 0 || buf[0].is_ascii_whitespace() {
                    break;
                }
                v.push(buf[0]);
            }
            Some(String::from_utf8(v).unwrap())
        }
    }

    pub fn next_line(&mut self) -> String {
        let mut line = String::new();
        self.reader.read_line(&mut line).unwrap();
        if let Some(s) = line.strip_suffix("\n") {
            s.to_string()
        } else {
            line
        }
    }

    pub fn vec<S: FromStr>(&mut self, size: i32) -> Vec<S> {
        let mut v: Vec<S> = vec![];
        for _ in 0..size {
            let token = self.next_str().unwrap();
            v.push(S::from_str(&token).ok().unwrap());
        }
        v
    }

    pub fn next_as<S: FromStr>(&mut self) -> Option<S> {
        let s = self.next_str()?;
        S::from_str(&s).ok()
    }

    pub fn str(&mut self) -> String {
        self.next_str().unwrap()
    }

    pub fn i32(&mut self) -> i32 {
        self.next_as::<i32>().unwrap()
    }

    pub fn u32(&mut self) -> u32 {
        self.next_as::<u32>().unwrap()
    }

    pub fn i64(&mut self) -> i64 {
        self.next_as::<i64>().unwrap()
    }

    pub fn u64(&mut self) -> u64 {
        self.next_as::<u64>().unwrap()
    }

    pub fn usize(&mut self) -> usize {
        self.next_as::<usize>().unwrap()
    }

    fn skip_whitespace(&mut self, mut buf: &mut [u8]) -> Option<u8> {
        loop {
            if !buf[0].is_ascii_whitespace() {
                return Some(buf[0]);
            }
            let size = self.reader.read(&mut buf).unwrap();
            if size == 0 {
                return None;
            }
        }
    }
}

struct XorShift32 {
    state: u32,
}

impl XorShift32 {
    fn from_seed(seed: u32) -> Self {
        let initial_state = if seed == 0 { 1 } else { seed };
        XorShift32 { state: initial_state }
    }

    fn next_u32(&mut self) -> u32 {
        let mut x = self.state;
        x ^= x << 13;
        x ^= x >> 17;
        x ^= x << 5;
        self.state = x;
        x
    }

    fn next_f64(&mut self) -> f64 {
        self.next_u32() as f64 / (u32::MAX as f64 + 1.0)
    }
}

#[derive(Debug)]
struct Timer {
    start_time: time::Instant,
    limit: time::Instant,
    before_time: Option<time::Instant>,
    worst_time: time::Duration,
}

impl Timer {
    fn new(tl: u64) -> Timer {
        let start_time = time::Instant::now();
        Timer {
            start_time,
            limit: start_time + time::Duration::from_millis(tl),
            before_time: None,
            worst_time: time::Duration::from_millis(0),
        }
    }

    fn elapsed(&self) -> u64 {
        self.start_time.elapsed().as_millis() as u64
    }

    fn checkpoint(&mut self) {
        if let Some(before_time) = self.before_time {
            let elapsed = before_time.elapsed();
            self.worst_time = self.worst_time.max(elapsed);
        }
        self.before_time = Some(time::Instant::now());
    }

    fn tl(&self) -> u64 {
        (self.limit - self.start_time).as_millis() as u64
    }

    fn tl_exceeded(&self) -> bool {
        self.limit < time::Instant::now()
    }

    fn should_stop(&self) -> bool {
        self.limit < time::Instant::now() + self.worst_time
    }
}

#[derive(Debug)]
struct FastClearingArray<T> {
    v: [[T; N + 2]; N + 2],
    gen: [[i32; N + 2]; N + 2],
    cur_gen: i32,
}

impl<T: Copy> FastClearingArray<T> {
    fn new(init: T) -> FastClearingArray<T> {
        FastClearingArray {
            v: [[init; N + 2]; N + 2],
            gen: [[0; N + 2]; N + 2],
            cur_gen: 0,
        }
    }

    fn clear(&mut self) {
        self.cur_gen += 1;
    }

    fn visited(&self, r: usize, c: usize) -> bool {
        self.gen[r][c] == self.cur_gen
    }

    fn get(&self, r: usize, c: usize) -> T {
        self.v[r][c]
    }

    fn set(&mut self, r: usize, c: usize, v: T) {
        self.v[r][c] = v;
        self.gen[r][c] = self.cur_gen;
    }
}

#[derive(Debug, Clone, Copy, PartialEq, Eq)]
struct Pos {
    y: usize,
    x: usize,
}

impl Pos {
    fn new(y: usize, x: usize) -> Pos {
        Pos { y, x }
    }
    fn dist(self, other: Pos) -> i32 {
        (self.y as i32 - other.y as i32).abs() + (self.x as i32 - other.x as i32).abs()
    }
}

#[derive(Debug, Clone, Copy)]
enum Action {
    Up,
    Right,
    Down,
    Left,
    Write,
    Copy,
}

#[derive(Debug, Clone)]
struct Input {
    a: Vec<Vec<u32>>,
}

impl Input {
    fn new() -> Input {
        let mut sc = scanner();
        let _ = sc.usize();
        let _ = sc.usize();
        let mut a = vec![];
        for _ in 0..N {
            let mut row = vec![];
            for _ in 0..N {
                row.push(sc.u32());
            }
            a.push(row);
        }
        Input { a }
    }
}

#[derive(Debug, Clone)]
struct Result {
    actions: Vec<Action>,
    score: i64,
}

impl Result {
    fn new(actions: Vec<Action>, score: i64) -> Result {
        Result { actions, score }
    }

    fn new_empty() -> Result {
        Result {
            actions: vec![],
            score: -1,
        }
    }

    fn output(&self) {
        for &a in &self.actions {
            match a {
                Action::Up => println!("U"),
                Action::Right => println!("R"),
                Action::Down => println!("D"),
                Action::Left => println!("L"),
                Action::Write => println!("W"),
                Action::Copy => println!("C"),
            }
        }
    }
}

struct Solver {
    input: Input,
    timer: Timer,
    rng: XorShift32,
}

impl Solver {
    fn new(input: Input) -> Solver {
        let tl = env::var("TL").map_or(TIMELIMIT, |v| v.parse().unwrap());
        let timer = Timer::new(tl);
        let rng = XorShift32::from_seed(2);
        Solver { input, timer, rng }
    }

    fn solve(&mut self, tl: u64) -> Result {
        let mut best_res = self.solve_single();
        eprintln!("score:{:?} turn:{:?}", best_res.score, -1);
        let mut turn = 0;
        loop {
            if self.timer.elapsed() > tl {
                eprintln!("solve_single turn:{:?}", turn);
                break;
            }
            let res = self.solve_single();
            if res.score > best_res.score {
                eprintln!("score:{:?} turn:{:?}", res.score, turn,);
                best_res = res;
            }
            turn += 1;
        }
        best_res
    }

    fn move_to(&mut self, cy: &mut usize, cx: &mut usize, ny: usize, nx: usize, acts: &mut Vec<Action>) {
        while *cy < ny {
            acts.push(Action::Down);
            *cy += 1;
        }
        while *cy > ny {
            acts.push(Action::Up);
            *cy -= 1;
        }
        while *cx < nx {
            acts.push(Action::Right);
            *cx += 1;
        }
        while *cx > nx {
            acts.push(Action::Left);
            *cx -= 1;
        }
    }

    fn tsp(&mut self, cy: usize, cx: usize, pos: &Vec<Pos>) -> Vec<Pos> {
        let mut order = pos.clone();
        for i in 0..order.len() - 1 {
            let pos = self.rng.next_u32() as usize % (order.len() - i) + i;
            order.swap(i, pos);
        }
        for turn in 0..100000 {
            let mut p0 = self.rng.next_u32() as usize % order.len();
            let mut p1 = self.rng.next_u32() as usize % (order.len() - 1);
            if p1 >= p0 {
                p1 += 1;
            } else {
                mem::swap(&mut p0, &mut p1);
            }
            let mut diff = 0;
            if p0 == 0 {
                diff -= (order[p0].y as i32 - cy as i32).abs() + (order[p0].x as i32 - cx as i32).abs();
                diff += (order[p1].y as i32 - cy as i32).abs() + (order[p1].x as i32 - cx as i32).abs();
            } else {
                diff -= order[p0].dist(order[p0 - 1]);
                diff += order[p1].dist(order[p0 - 1]);
            }
            if p1 < pos.len() - 1 {
                diff -= order[p1].dist(order[p1 + 1]);
                diff += order[p0].dist(order[p1 + 1]);
            } else {
                diff -= (order[p1].y as i32 - cy as i32).abs() + (order[p1].x as i32 - cx as i32).abs();
                diff += (order[p0].y as i32 - cy as i32).abs() + (order[p0].x as i32 - cx as i32).abs();
            }
            if diff <= 0 || self.rng.next_f64() < (-diff as f64 * turn as f64 * 0.0001).exp() {
                if let Some(slice) = order.get_mut(p0..=p1) {
                    slice.reverse();
                }
            }
        }
        order
    }

    fn select_base(&mut self) -> Vec<Pos> {
        let mut a = self.input.a.clone();
        let mut base_pos = vec![];
        let mut best_score = 0;
        let mut best_base_pos = vec![];
        for _ in 0..10000 {
            for i in 0..N {
                a[i].copy_from_slice(self.input.a[i].as_slice());
            }
            let mut cy = 0;
            let mut cx = 0;
            base_pos.clear();
            for bi in (13..=19).rev() {
                // let mut min_d = N as i32 * 2;
                let mut cand_pos = vec![];
                for y in 0..N {
                    for x in 0..N {
                        let v = a[y][x];
                        if (v & (1 << bi)) != 0 && v & (0xFFFFE << bi) == 0 {
                            let d = (y as i32 - cy as i32).abs() + (x as i32 - cx as i32).abs();
                            if d < 10 {
                                cand_pos.push(Pos::new(y, x));
                            }
                            // if d < min_d {
                            //     min_d = d;
                            //     cand_pos.clear();
                            //     cand_pos.push(Pos::new(y, x));
                            // } else if d <= min_d + 1 {
                            //     cand_pos.push(Pos::new(y, x));
                            // }
                        }
                    }
                }
                let target = cand_pos[self.rng.next_u32() as usize % cand_pos.len()];
                base_pos.push(target);
                cy = target.y;
                cx = target.x;
                for y in 0..N {
                    for x in 0..N {
                        if (y != cy || x != cx) && (a[y][x] & (1 << bi)) != 0 {
                            a[y][x] ^= a[cy][cx];
                        }
                    }
                }
            }
            let mut s = 0;
            for p in base_pos.iter() {
                s ^= a[p.y][p.x];
            }
            let mut score = 0;
            for y in 0..N {
                for x in 0..N {
                    if (a[y][x] & 0xFE000) == 0 {
                        score += a[y][x] ^ s;
                    }
                }
            }
            // let score = a.iter().flatten().map(|&v| v as i64).sum::<i64>();
            if score > best_score {
                // eprintln!("tmp_score:{:?}", score);
                best_score = score;
                best_base_pos = base_pos.clone();
            }
        }
        best_base_pos
    }

    fn solve_single(&mut self) -> Result {
        let mut cy = 0;
        let mut cx = 0;
        let mut acts = vec![];
        let mut a = self.input.a.clone();
        let mut s = 0;
        let base_pos = self.select_base();
        let mut is_base = vec![vec![false; N]; N];
        for p in &base_pos {
            is_base[p.y][p.x] = true;
        }
        for bi in (13..=19).rev() {
            let target = base_pos[19 - bi];
            self.move_to(&mut cy, &mut cx, target.y, target.x, &mut acts);
            s ^= a[cy][cx];
            acts.push(Action::Copy);
            if acts.len() >= T {
                break;
            }
            let mut pos = vec![];
            for y in 0..N {
                for x in 0..N {
                    if y == cy && x == cx {
                        continue;
                    }
                    if is_base[y][x] ^ ((a[y][x] & (1 << bi)) == 0) {
                        pos.push(Pos::new(y, x));
                    }
                }
            }
            let order = self.tsp(cy, cx, &pos);
            for p in order {
                self.move_to(&mut cy, &mut cx, p.y, p.x, &mut acts);
                if acts.len() >= T {
                    break;
                }
                a[p.y][p.x] ^= s;
                acts.push(Action::Write);
            }
            self.move_to(&mut cy, &mut cx, target.y, target.x, &mut acts);
            s ^= a[cy][cx];
            acts.push(Action::Copy);
            if acts.len() >= T {
                break;
            }
        }
        // eprintln!("acts_len after prepare:{:?}", acts.len());
        for p in base_pos.iter().rev() {
            self.move_to(&mut cy, &mut cx, p.y, p.x, &mut acts);
            s ^= a[cy][cx];
            acts.push(Action::Copy);
        }
        // self.debug_print(s, &a);
        // let mut pos = vec![];
        // for y in 0..N {
        //     for x in 0..N {
        //         if y != cy || x != cx {
        //             pos.push(Pos::new(y, x));
        //         }
        //     }
        // }

        let order = self.tsp(cy, cx, &base_pos[1..].to_vec());
        for p in order {
            self.move_to(&mut cy, &mut cx, p.y, p.x, &mut acts);
            if acts.len() >= T {
                break;
            }
            a[p.y][p.x] ^= s;
            acts.push(Action::Write);
        }
        self.move_to(&mut cy, &mut cx, base_pos[0].y, base_pos[0].x, &mut acts);
        s ^= a[cy][cx];
        acts.push(Action::Copy);
        a[cy][cx] ^= s;
        acts.push(Action::Write);
        eprintln!("acts_len:{:?}", acts.len());
        if acts.len() > T {
            return Result::new_empty();
        }
        for i in 2..base_pos.len() {
            self.move_to(&mut cy, &mut cx, base_pos[i].y, base_pos[i].x, &mut acts);
            s ^= a[cy][cx];
            acts.push(Action::Copy);
        }
        self.move_to(&mut cy, &mut cx, base_pos[1].y, base_pos[1].x, &mut acts);
        // self.debug_print(s, &a);
        if acts.len() < T {
            a[cy][cx] ^= s;
            acts.push(Action::Write);
        }
        if acts.len() > T {
            acts.truncate(T);
        }
        let score = a.iter().flatten().map(|&v| v as i64).sum::<i64>();
        // self.debug_print(s, &a);
        eprintln!("score:{:?}", score);
        Result::new(acts, score)
    }

    fn debug_print(&self, s: u32, a: &Vec<Vec<u32>>) {
        eprintln!("s:{:x}", s);
        for row in a {
            for &v in row {
                eprint!("{:05x} ", v);
            }
            eprintln!();
        }
    }
}

fn main() {
    let input = Input::new();
    let mut solver = Solver::new(input.clone());
    let mut best_res = Result::new_empty();
    let part = env::var("PART").map_or(1, |v| v.parse().unwrap());
    for i in 0..part {
        let result = solver.solve(solver.timer.tl() * (i + 1) / part);
        if result.score > best_res.score {
            best_res = result;
        }
        break;
    }
    best_res.output();
    eprintln!("final_score:{:?} ", best_res.score);
}
yukicoder

結果

ソースコード
