#629285 (Rust) No.1427 Simplified Tetris

提出ソース

結果

問題	No.1427 Simplified Tetris
ユーザー	akakimidori
提出日時	2021-03-13 14:49:05
言語	Rust (1.77.0 + proconio)
結果	AC
実行時間	15 ms / 2,000 ms
コード長	8,131 bytes
コンパイル時間	13,776 ms
コンパイル使用メモリ	379,832 KB
実行使用メモリ	5,248 KB
最終ジャッジ日時	2024-10-15 06:21:24
合計ジャッジ時間	15,721 ms
ジャッジサーバーID （参考情報）	judge5 / judge3

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	1 ms 5,248 KB
testcase_01	AC	1 ms 5,248 KB
testcase_02	AC	2 ms 5,248 KB
testcase_03	AC	1 ms 5,248 KB
testcase_04	AC	1 ms 5,248 KB
testcase_05	AC	1 ms 5,248 KB
testcase_06	AC	1 ms 5,248 KB
testcase_07	AC	1 ms 5,248 KB
testcase_08	AC	1 ms 5,248 KB
testcase_09	AC	1 ms 5,248 KB
testcase_10	AC	1 ms 5,248 KB
testcase_11	AC	14 ms 5,248 KB
testcase_12	AC	1 ms 5,248 KB
testcase_13	AC	1 ms 5,248 KB
testcase_14	AC	1 ms 5,248 KB
testcase_15	AC	1 ms 5,248 KB
testcase_16	AC	1 ms 5,248 KB
testcase_17	AC	1 ms 5,248 KB
testcase_18	AC	1 ms 5,248 KB
testcase_19	AC	2 ms 5,248 KB
testcase_20	AC	1 ms 5,248 KB
testcase_21	AC	0 ms 5,248 KB
testcase_22	AC	1 ms 5,248 KB
testcase_23	AC	1 ms 5,248 KB
testcase_24	AC	1 ms 5,248 KB
testcase_25	AC	1 ms 5,248 KB
testcase_26	AC	1 ms 5,248 KB
testcase_27	AC	1 ms 5,248 KB
testcase_28	AC	1 ms 5,248 KB
testcase_29	AC	1 ms 5,248 KB
testcase_30	AC	1 ms 5,248 KB
testcase_31	AC	1 ms 5,248 KB
testcase_32	AC	11 ms 5,248 KB
testcase_33	AC	5 ms 5,248 KB
testcase_34	AC	1 ms 5,248 KB
testcase_35	AC	1 ms 5,248 KB
testcase_36	AC	12 ms 5,248 KB
testcase_37	AC	1 ms 5,248 KB
testcase_38	AC	15 ms 5,248 KB
testcase_39	AC	14 ms 5,248 KB
testcase_40	AC	12 ms 5,248 KB

権限があれば一括ダウンロードができます

ソースコード

raw source code

// ---------- begin max flow (Dinic) ----------
mod maxflow {
    pub trait MaxFlowCapacity:
        Copy + Ord + std::ops::Add<Output = Self> + std::ops::Sub<Output = Self>
    {
        fn zero() -> Self;
        fn inf() -> Self;
    }

    macro_rules! impl_primitive_integer_capacity {
        ($x:ty, $y:expr) => {
            impl MaxFlowCapacity for $x {
                fn zero() -> Self {
                    0
                }
                fn inf() -> Self {
                    $y
                }
            }
        };
    }

    impl_primitive_integer_capacity!(u32, std::u32::MAX);
    impl_primitive_integer_capacity!(u64, std::u64::MAX);
    impl_primitive_integer_capacity!(i32, std::i32::MAX);
    impl_primitive_integer_capacity!(i64, std::i64::MAX);

    #[derive(Clone)]
    struct Edge<Cap> {
        to_: u32,
        inv_: u32,
        cap_: Cap,
    }

    impl<Cap> Edge<Cap> {
        fn new(to: usize, inv: usize, cap: Cap) -> Self {
            Edge {
                to_: to as u32,
                inv_: inv as u32,
                cap_: cap,
            }
        }
        fn to(&self) -> usize {
            self.to_ as usize
        }
        fn inv(&self) -> usize {
            self.inv_ as usize
        }
    }

    impl<Cap: MaxFlowCapacity> Edge<Cap> {
        fn add(&mut self, cap: Cap) {
            self.cap_ = self.cap_ + cap;
        }
        fn sub(&mut self, cap: Cap) {
            self.cap_ = self.cap_ - cap;
        }
        fn cap(&self) -> Cap {
            self.cap_
        }
    }

    pub struct Graph<Cap> {
        graph: Vec<Vec<Edge<Cap>>>,
    }

    #[allow(dead_code)]
    pub struct EdgeIndex {
        src: usize,
        dst: usize,
        x: usize,
        y: usize,
    }

    impl<Cap: MaxFlowCapacity> Graph<Cap> {
        pub fn new(size: usize) -> Self {
            Self {
                graph: vec![vec![]; size],
            }
        }
        pub fn add_edge(&mut self, src: usize, dst: usize, cap: Cap) -> EdgeIndex {
            assert!(src.max(dst) < self.graph.len());
            assert!(cap >= Cap::zero());
            assert!(src != dst);
            let x = self.graph[src].len();
            let y = self.graph[dst].len();
            self.graph[src].push(Edge::new(dst, y, cap));
            self.graph[dst].push(Edge::new(src, x, Cap::zero()));
            EdgeIndex { src, dst, x, y }
        }
        // src, dst, used, intial_capacity
        #[allow(dead_code)]
        pub fn get_edge(&self, e: &EdgeIndex) -> (usize, usize, Cap, Cap) {
            let max = self.graph[e.src][e.x].cap() + self.graph[e.dst][e.y].cap();
            let used = self.graph[e.dst][e.y].cap();
            (e.src, e.dst, used, max)
        }
        pub fn flow(&mut self, src: usize, dst: usize) -> Cap {
            let size = self.graph.len();
            assert!(src.max(dst) < size);
            assert!(src != dst);
            let mut queue = std::collections::VecDeque::new();
            let mut level = vec![0; size];
            let mut it = vec![0; size];
            let mut ans = Cap::zero();
            loop {
                (|| {
                    level.clear();
                    level.resize(size, 0);
                    level[src] = 1;
                    queue.clear();
                    queue.push_back(src);
                    while let Some(v) = queue.pop_front() {
                        let d = level[v] + 1;
                        for e in self.graph[v].iter() {
                            let u = e.to();
                            if e.cap() > Cap::zero() && level[u] == 0 {
                                level[u] = d;
                                if u == dst {
                                    return;
                                }
                                queue.push_back(u);
                            }
                        }
                    }
                })();
                if level[dst] == 0 {
                    break;
                }
                it.clear();
                it.resize(size, 0);
                loop {
                    let f = self.dfs(dst, src, Cap::inf(), &mut it, &level);
                    if f == Cap::zero() {
                        break;
                    }
                    ans = ans + f;
                }
            }
            ans
        }
        fn dfs(&mut self, v: usize, src: usize, cap: Cap, it: &mut [usize], level: &[u32]) -> Cap {
            if v == src {
                return cap;
            }
            while let Some((u, inv)) = self.graph[v].get(it[v]).map(|p| (p.to(), p.inv())) {
                if level[u] + 1 == level[v] && self.graph[u][inv].cap() > Cap::zero() {
                    let cap = cap.min(self.graph[u][inv].cap());
                    let c = self.dfs(u, src, cap, it, level);
                    if c > Cap::zero() {
                        self.graph[v][it[v]].add(c);
                        self.graph[u][inv].sub(c);
                        return c;
                    }
                }
                it[v] += 1;
            }
            Cap::zero()
        }
    }
}
// ---------- end max flow (Dinic) ----------

fn read() -> Vec<Vec<char>> {
    let mut s = String::new();
    use std::io::Read;
    std::io::stdin().read_to_string(&mut s).unwrap();
    let mut it = s.trim().split_whitespace();
    it.next();
    it.next();
    it.map(|s| s.chars().collect::<Vec<_>>()).collect()
}

fn main() {
    let s = read();
    if s.iter().flatten().all(|c| *c == '.') {
        println!("Yes");
        for _ in 0..s.len() {
            println!("{}", ".".repeat(s[0].len()));
        }
        return;
    }
    let mut cond = true;
    cond &= s.iter().all(|s| !s.iter().all(|s| *s == '#'));
    let x = s.iter().rposition(|s| s.iter().all(|s| *s == '.')).map_or(0, |x| x + 1);
    cond &= s[..x].iter().flatten().all(|c| *c == '.');
    if !cond {
        println!("No");
        return;
    }
    let (h, w) = (s.len(), s[0].len());
    let cnt = h - x;
    for i in 0usize..(1 << h) {
        if i.count_ones() as usize + cnt > h {
            continue;
        }
        let mut board = vec![vec!['.'; w]; h];
        let mut p = h - 1;
        for (j, b) in board.iter_mut().rev().enumerate() {
            if i >> j & 1 == 1 {
                *b = vec!['#'; w];
            } else if s[p].iter().any(|s| *s == '#') {
                *b = s[p].clone();
                p -= 1;
            }
        }
        let s = &board;
        let mut g = maxflow::Graph::new(h * w + 2);
        let src = h * w;
        let dst = src + 1;
        let mut edge = vec![];
        for i in 0..h {
            for j in 0..w {
                if s[i][j] == '.' {
                    continue;
                }
                if (i + j) & 1 == 0 {
                    g.add_edge(i * w + j, dst, 1);
                } else {
                    g.add_edge(src, i * w + j, 1);
                    for &(x, y) in [(i - 1, j), (i + 1, j), (i, j - 1), (i, j + 1)].iter() {
                        if x < h && y < w && s[x][y] == '#' {
                            edge.push(g.add_edge(i * w + j, x * w + y, 1));
                        }
                    }
                }
            }
        }
        let count = s.iter().flatten().filter(|c| **c == '#').count() as u32;
        let flow = g.flow(src, dst);
        if 2 * flow == count {
            let mut op = vec![];
            op.extend(b'a'..=b'z');
            op.extend(b'A'..=b'Z');
            let mut x = 0;
            let mut ans = vec![vec![b'.'; w]; h];
            for e in edge.iter() {
                let (s, t, u, _) = g.get_edge(e);
                if u == 1 {
                    let c = op[x];
                    x += 1;
                    ans[s / w][s % w] = c;
                    ans[t / w][t % w] = c;
                }
            }
            println!("Yes");
            for ans in ans {
                let ans = ans.into_iter().map(|c| c as char).collect::<String>();
                println!("{}", ans);
            }
            return;
        }
    }
    println!("No");
}

yukicoder

結果

テストケース

ソースコード