結果

問題 No.5019 Hakai Project
ユーザー hangryhangry
提出日時 2023-11-17 21:56:02
言語 Rust
(1.77.0)
結果
AC  
実行時間 1,000 ms / 3,000 ms
コード長 14,026 bytes
コンパイル時間 2,255 ms
コンパイル使用メモリ 200,452 KB
実行使用メモリ 384,640 KB
スコア 807,209,638
最終ジャッジ日時 2023-11-17 21:56:49
合計ジャッジ時間 46,039 ms
ジャッジサーバーID
（参考情報） 		judge13 / judge11
純コード判定しない問題か言語
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 866 ms
335,360 KB
testcase_01 AC 827 ms
324,992 KB
testcase_02 AC 1,000 ms
384,640 KB
testcase_03 AC 594 ms
242,176 KB
testcase_04 AC 845 ms
324,480 KB
testcase_05 AC 716 ms
286,720 KB
testcase_06 AC 592 ms
237,312 KB
testcase_07 AC 869 ms
332,672 KB
testcase_08 AC 728 ms
289,792 KB
testcase_09 AC 788 ms
311,680 KB
testcase_10 AC 551 ms
221,568 KB
testcase_11 AC 730 ms
294,656 KB
testcase_12 AC 722 ms
286,208 KB
testcase_13 AC 719 ms
278,400 KB
testcase_14 AC 736 ms
296,576 KB
testcase_15 AC 519 ms
227,072 KB
testcase_16 AC 739 ms
291,968 KB
testcase_17 AC 745 ms
305,792 KB
testcase_18 AC 705 ms
276,480 KB
testcase_19 AC 738 ms
287,360 KB
testcase_20 AC 731 ms
299,520 KB
testcase_21 AC 804 ms
310,400 KB
testcase_22 AC 670 ms
269,184 KB
testcase_23 AC 734 ms
295,936 KB
testcase_24 AC 993 ms
377,472 KB
testcase_25 AC 713 ms
286,592 KB
testcase_26 AC 792 ms
317,440 KB
testcase_27 AC 855 ms
336,768 KB
testcase_28 AC 647 ms
260,608 KB
testcase_29 AC 642 ms
259,200 KB
testcase_30 AC 640 ms
256,768 KB
testcase_31 AC 594 ms
229,888 KB
testcase_32 AC 632 ms
257,536 KB
testcase_33 AC 870 ms
338,816 KB
testcase_34 AC 782 ms
294,144 KB
testcase_35 AC 698 ms
272,256 KB
testcase_36 AC 637 ms
258,560 KB
testcase_37 AC 572 ms
227,712 KB
testcase_38 AC 456 ms
191,488 KB
testcase_39 AC 961 ms
369,024 KB
testcase_40 AC 814 ms
313,344 KB
testcase_41 AC 875 ms
348,544 KB
testcase_42 AC 634 ms
263,808 KB
testcase_43 AC 924 ms
363,392 KB
testcase_44 AC 711 ms
282,496 KB
testcase_45 AC 579 ms
241,536 KB
testcase_46 AC 794 ms
305,152 KB
testcase_47 AC 789 ms
303,360 KB
testcase_48 AC 694 ms
280,832 KB
testcase_49 AC 820 ms
321,920 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#![allow(dead_code)]
#![allow(non_upper_case_globals)]
#![allow(unused_imports)]
use grid::{Coord, Map2d, DC};
use std::cmp::*;
use std::collections::*;
use std::io::stdin;

const TIME_LIMIT: f64 = 2.9;
const N: usize = 50;
const N2: usize = N * N;
const M: usize = 20;

pub fn main() {
    get_time();
    let input = read_input();
    let output = solve(&input);
    output.print_ans();
    eprintln!("Time = {}", get_time());
}

fn solve(input: &Input) -> Output {
    let mut state = State::new(input);
    state.calc_score(input);
    state.to_output(input)
}

struct State {
    score: usize,
    use_bomb: Map2d<Vec<bool>>,
    cnt_use: Map2d<usize>,
    jun: Vec<(Coord, usize)>,
}

impl State {
    fn new(input: &Input) -> Self {
        let score = !0;
        let mut use_bomb = Map2d::new(vec![vec![false; M]; N2], N);
        let mut cnt_use = Map2d::new(vec![0; N2], N);
        let mut jun = vec![];
        for x in 0..N {
            for y in 0..N {
                let p = Coord::new(x, y);
                if input.map[p] == Square::Empty || cnt_use[p] > 0 {
                    continue;
                }
                let (bp, bid) = input.can_hakai_rev[p][rnd::next() % input.can_hakai_rev[p].len()];
                use_bomb[bp][bid] = true;
                for &np in input.can_hakai[bp][bid].iter() {
                    cnt_use[np] += 1;
                }
                jun.push((bp, bid));
            }
        }
        Self {
            score,
            use_bomb,
            cnt_use,
            jun,
        }
    }

    fn calc_score(&mut self, input: &Input) {
        let mut score = 0;
        let sz = self.jun.len();
        // uso dp
        let mut dp = 0;
        let mut rui = 0;
        let mut mae = Coord::new(0, 0);
        let mut bombed = Map2d::new(vec![false; N2], N);
        for i in 0..sz {
            score += input.bomb_cost[self.jun[i].1];
            let ue = if i == 0 {
                (!0, !0)
            } else {
                (
                    dp + rui + self.jun[i].0.dist(&mae),
                    rui + self.jun[i].0.dist(&mae),
                )
            };
            let sita = if let Some(&near) = input.near_shop[self.jun[i].0]
                .iter()
                .find(|&&np| !bombed[np])
            {
                (
                    dp + mae.dist(&near) + self.jun[i].0.dist(&near),
                    self.jun[i].0.dist(&near),
                )
            } else {
                (!0, !0)
            };
            if ue.0 < sita.0 {
                dp = ue.0;
                rui = ue.1;
            } else {
                dp = sita.0;
                rui = sita.1;
            }
            mae = self.jun[i].0;
            for &np in input.can_hakai[self.jun[i].0][self.jun[i].1].iter() {
                bombed[np] = true;
            }
        }

        self.score = score + dp;
    }

    fn to_output(&self, input: &Input) -> Output {
        let mut actions = vec![];
        let sz = self.jun.len();

        let mut dp = 0;
        let mut rui = 0;
        let mut mae = Coord::new(0, 0);
        let mut bombed = Map2d::new(vec![false; N2], N);
        let mut buyvec = vec![];
        for i in 0..sz {
            let ue = if i == 0 {
                (!0, !0)
            } else {
                (
                    dp + rui + self.jun[i].0.dist(&mae),
                    rui + self.jun[i].0.dist(&mae),
                )
            };
            let sita = if let Some(&near) = input.near_shop[self.jun[i].0]
                .iter()
                .find(|&&np| !bombed[np])
            {
                (
                    dp + mae.dist(&near) + self.jun[i].0.dist(&near),
                    self.jun[i].0.dist(&near),
                )
            } else {
                (!0, !0)
            };
            if ue.0 < sita.0 {
                dp = ue.0;
                rui = ue.1;
                actions.extend(moves(mae, self.jun[i].0));
            } else {
                dp = sita.0;
                rui = sita.1;
                let near = *input.near_shop[self.jun[i].0]
                    .iter()
                    .find(|&&np| !bombed[np])
                    .unwrap();
                actions.extend(moves(mae, near));
                // ここに購入を計算 todo // あとでここに入れる
                buyvec.push(vec![]);
                actions.push((2, !0));
                //
                actions.extend(moves(near, self.jun[i].0));
            }
            // use
            actions.push((3, self.jun[i].1 + 1));
            let lll = buyvec.len() - 1;
            buyvec[lll].push((2, self.jun[i].1 + 1));
            //
            mae = self.jun[i].0;
            for &np in input.can_hakai[self.jun[i].0][self.jun[i].1].iter() {
                bombed[np] = true;
            }
        }
        let mut ret_actions = vec![];
        let mut buyidx = 0;
        for &(tp, dd) in actions.iter() {
            if tp != 2 {
                ret_actions.push((tp, dd));
            } else {
                for &t in buyvec[buyidx].iter() {
                    ret_actions.push(t);
                }
                buyidx += 1;
            }
        }
        Output {
            score: self.score,
            actions: ret_actions,
        }
    }
}

fn moves(a: Coord, b: Coord) -> Vec<(usize, usize)> {
    let mut ret = vec![];
    let mut p = a;
    while p != b {
        if p.y > b.y {
            p.y -= 1;
            ret.push((1, 0));
        } else if p.x > b.x {
            p.x -= 1;
            ret.push((1, 1));
        } else if p.y < b.y {
            p.y += 1;
            ret.push((1, 2));
        } else if p.x < b.x {
            p.x += 1;
            ret.push((1, 3));
        };
    }
    ret
}

#[derive(PartialEq, Eq, Clone, Copy)]
enum Square {
    Empty,
    House,
    Shop,
}

struct Input {
    map: Map2d<Square>,
    bomb_cost: Vec<usize>,
    near_shop: Map2d<Vec<Coord>>,
    can_hakai: Map2d<Vec<Vec<Coord>>>, // そのマスで爆弾iを使って破壊できるもの
    can_hakai_rev: Map2d<Vec<(Coord, usize)>>, // そのマスを破壊することができるマスと爆弾の種類
}

fn read_input() -> Input {
    let _nm = input_vecusize();
    let mut map_ = vec![];
    for _i in 0..N {
        let a = input_string();
        map_.push(a.chars().collect::<Vec<_>>());
    }
    let mut map = vec![];
    for x in 0..N {
        for y in 0..N {
            let c = match map_[x][y] {
                '.' => Square::Empty,
                '#' => Square::House,
                '@' => Square::Shop,
                _ => unreachable!(),
            };
            map.push(c);
        }
    }
    let map = Map2d::new(map, N);
    let mut can_hakai = Map2d::new(vec![vec![vec![]; M]; N2], N);
    let mut bomb_cost = vec![];
    let mut can_hakai_rev = Map2d::new(vec![vec![]; N2], N);
    for bombid in 0..M {
        let cl = input_vecusize();
        let c = cl[0];
        let l = cl[1];
        bomb_cost.push(c);
        for _ in 0..l {
            let dxdy = input_veci32();
            let dx = dxdy[0];
            let dy = dxdy[1];
            for x in 0..N as i32 {
                for y in 0..N as i32 {
                    let nx = x + dx;
                    let ny = y + dy;
                    let p = Coord::new(x as usize, y as usize);
                    let np = Coord::new(nx as usize, ny as usize);
                    if 0 <= nx
                        && nx < N as i32
                        && 0 <= ny
                        && ny < N as i32
                        && map[np] != Square::Empty
                    {
                        can_hakai[p][bombid].push(np);
                        can_hakai_rev[np].push((p, bombid));
                    }
                }
            }
        }
    }
    let mut near_shop = Map2d::new(vec![vec![]; N2], N);
    let mut shops = vec![];
    for x in 0..N {
        for y in 0..N {
            let p = Coord::new(x, y);
            if map[p] == Square::Shop {
                shops.push(p);
            }
        }
    }
    for x in 0..N {
        for y in 0..N {
            let p = Coord::new(x, y);
            near_shop[p] = shops.clone();
            near_shop[p].sort_by(|a, b| p.dist(a).cmp(&p.dist(b)));
        }
    }

    Input {
        map,
        bomb_cost,
        near_shop,
        can_hakai,
        can_hakai_rev,
    }
}

struct Output {
    score: usize,
    actions: Vec<(usize, usize)>,
}

impl Output {
    fn print_ans(&self) {
        let score = self.score;
        crate::print_data!(score);
        let q = self.actions.len();
        println!("{}", q);
        for i in 0..q {
            if self.actions[i].0 == 1 {
                println!("{} {}", self.actions[i].0, DC[self.actions[i].1]);
            } else {
                println!("{} {}", self.actions[i].0, self.actions[i].1);
            }
        }
    }
}

// ここからライブラリ
#[macro_export]
macro_rules! print_data {
    ( $($x:expr),* ) => {{
        $(eprintln!("[DATA] {} = {:?}", stringify!($x), $x);)*
    }}
}

pub fn get_time() -> f64 {
    static mut START: f64 = -1.0;
    let end = std::time::SystemTime::now()
        .duration_since(std::time::UNIX_EPOCH)
        .unwrap()
        .as_secs_f64();
    unsafe {
        if START < 0.0 {
            START = end;
        }
        end - START
    }
}

#[allow(unused)]
mod rnd {
    static mut S: usize = 88172645463325252;

    pub fn next() -> usize {
        unsafe {
            S ^= S << 7;
            S ^= S >> 9;
            S
        }
    }

    pub fn nextf() -> f64 {
        f64::from_bits((0x3ff0000000000000 | next() & 0xfffffffffffff) as u64) - 1.
    }

    pub fn range(a: usize, b: usize) -> usize {
        next() % (b - a) + a
    }

    pub fn exu(a: usize, b: usize, skip: usize) -> usize {
        assert!(a <= skip && skip < b);
        let ret = range(a, b - 1);

        ret + (skip <= ret) as usize
    }

    pub fn rangei(a: i64, b: i64) -> i64 {
        (next() % ((b - a) as usize)) as i64 + a
    }

    pub fn shuffle<T>(list: &mut [T]) {
        for i in (0..list.len()).rev() {
            list.swap(i, next() % (i + 1));
        }
    }
}

#[allow(dead_code)]
mod grid {
    #[derive(Debug, Clone, Copy, PartialEq, Eq, PartialOrd, Ord)]
    pub struct Coord {
        pub x: usize,
        pub y: usize,
    }

    impl Coord {
        pub const fn new(x: usize, y: usize) -> Self {
            Self { x, y }
        }

        pub const fn new2(p: usize, width: usize) -> Self {
            Self {
                x: p / width,
                y: p % width,
            }
        }

        pub fn in_map(&self, size: usize) -> bool {
            self.x < size && self.y < size
        }

        pub const fn idx(&self, size: usize) -> usize {
            self.x * size + self.y
        }

        pub fn next(self, dir: usize) -> Self {
            self + DXY[dir]
        }

        pub const fn dist(&self, other: &Self) -> usize {
            Self::dist_1d(self.x, other.x) + Self::dist_1d(self.y, other.y)
        }

        const fn dist_1d(x0: usize, x1: usize) -> usize {
            x0.abs_diff(x1)
        }
    }

    impl std::ops::Add for Coord {
        type Output = Self;

        fn add(self, other: Self) -> Self {
            Self {
                x: self.x + other.x,
                y: self.y + other.y,
            }
        }
    }

    pub const DXY: [Coord; 4] = [
        Coord::new(0, !0),
        Coord::new(!0, 0),
        Coord::new(0, 1),
        Coord::new(1, 0),
    ];

    pub const DC: [char; 4] = ['L', 'U', 'R', 'D'];

    #[derive(Debug, Clone)]
    pub struct Map2d<T> {
        pub height: usize,
        pub width: usize,
        map: Vec<T>,
    }

    impl<T: Clone> Map2d<T> {
        pub fn new(map: Vec<T>, width: usize) -> Self {
            let height = map.len() / width;
            debug_assert!(width * height == map.len());
            Self { height, width, map }
        }

        pub fn fill(&mut self, value: T) {
            self.map.fill(value);
        }
    }

    impl<T> std::ops::Index<Coord> for Map2d<T> {
        type Output = T;

        #[inline]
        fn index(&self, coord: Coord) -> &Self::Output {
            unsafe { self.map.get_unchecked(coord.x * self.width + coord.y) }
        }
    }

    impl<T> std::ops::IndexMut<Coord> for Map2d<T> {
        #[inline]
        fn index_mut(&mut self, coord: Coord) -> &mut Self::Output {
            unsafe { self.map.get_unchecked_mut(coord.x * self.width + coord.y) }
        }
    }

    impl<T> std::ops::Index<&Coord> for Map2d<T> {
        type Output = T;

        #[inline]
        fn index(&self, coord: &Coord) -> &Self::Output {
            &self.map[coord.x * self.width + coord.y]
        }
    }

    impl<T> std::ops::IndexMut<&Coord> for Map2d<T> {
        #[inline]
        fn index_mut(&mut self, coord: &Coord) -> &mut Self::Output {
            &mut self.map[coord.x * self.width + coord.y]
        }
    }

    impl<T> std::ops::Index<usize> for Map2d<T> {
        type Output = T;

        #[inline]
        fn index(&self, p: usize) -> &Self::Output {
            &self.map[p]
        }
    }

    impl<T> std::ops::IndexMut<usize> for Map2d<T> {
        #[inline]
        fn index_mut(&mut self, p: usize) -> &mut Self::Output {
            &mut self.map[p]
        }
    }
}

fn input_vecusize() -> Vec<usize> {
    let mut a = String::new();
    stdin().read_line(&mut a).unwrap();
    return a
        .trim()
        .split_whitespace()
        .map(|e| e.parse().ok().unwrap())
        .collect();
}
fn input_veci32() -> Vec<i32> {
    let mut a = String::new();
    stdin().read_line(&mut a).unwrap();
    return a
        .trim()
        .split_whitespace()
        .map(|e| e.parse().ok().unwrap())
        .collect();
}

fn input_string() -> String {
    let mut a = String::new();
    stdin().read_line(&mut a).unwrap();
    return a.trim().parse().unwrap();
}
0