結果

問題 No.3335 ReCT
コンテスト
ユーザー cologne
提出日時 2025-11-11 19:30:48
言語 Rust
(1.83.0 + proconio)
結果
AC  
実行時間 12 ms / 2,000 ms
コード長 8,500 bytes
コンパイル時間 13,965 ms
コンパイル使用メモリ 399,672 KB
実行使用メモリ 7,716 KB
最終ジャッジ日時 2025-11-11 19:31:10
合計ジャッジ時間 20,994 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 97
権限があれば一括ダウンロードができます

ソースコード

diff # 

use std::iter::{once, repeat};

use fio::*;

fn transpose(a: Vec<Vec<usize>>) -> Vec<Vec<usize>> {
    let h = a.len();
    let w = a[0].len();
    let mut ret = vec![vec![0; h]; w];
    for r in 0..h {
        for c in 0..w {
            ret[c][r] = a[r][c];
        }
    }
    ret
}

fn merge_vert(
    a1: (usize, Vec<Vec<usize>>),
    a2: (usize, Vec<Vec<usize>>),
) -> (usize, Vec<Vec<usize>>) {
    assert_eq!(a1.1[0].len(), a2.1[0].len());
    let mut w = a1.1;
    w.extend(
        a2.1.into_iter()
            .map(|r| r.into_iter().map(|x| x + a1.0).collect()),
    );
    (a1.0 + a2.0, w)
}

fn merge_horz(
    a1: (usize, Vec<Vec<usize>>),
    a2: (usize, Vec<Vec<usize>>),
) -> (usize, Vec<Vec<usize>>) {
    assert_eq!(a1.1.len(), a2.1.len());

    let w: Vec<Vec<usize>> =
        a1.1.into_iter()
            .zip(a2.1.into_iter())
            .map(|(mut r1, r2)| {
                r1.extend(r2.into_iter().map(|x| x + a1.0));
                r1
            })
            .collect();
    (a1.0 + a2.0, w)
}

fn get_c(n: usize, m: usize) -> Option<(usize, Vec<Vec<usize>>)> {
    if n > m {
        return get_c(m, n).map(|(k, ret)| (k, transpose(ret)));
    }

    if n <= 2 {
        return None;
    }

    if n == 3 {
        if m % 2 == 1 {
            return None;
        }
        if m == 4 {
            return Some((
                2,
                vec![vec![1, 1, 1, 2], vec![1, 2, 1, 2], vec![1, 2, 2, 2]],
            ));
        }
        if m == 6 {
            return Some((
                3,
                vec![
                    vec![1, 2, 2, 2, 2, 3],
                    vec![1, 2, 1, 3, 2, 3],
                    vec![1, 1, 1, 3, 3, 3],
                ],
            ));
        }
        let a1 = get_c(n, m - 4).unwrap();
        let a2 = get_c(n, 4).unwrap();
        return Some(merge_horz(a1, a2));
    }

    if n == 4 {
        return Some((
            2,
            vec![
                vec![1; m],
                repeat(2).take(m - 1).chain(once(1)).collect(),
                once(2).chain(repeat(1).take(m - 1)).collect(),
                vec![2; m],
            ],
        ));
    }

    let (v, mut a) = get_c(n - 1, m - 2).unwrap();

    for x in a.iter_mut() {
        x.insert(0, v + 1);
        x.push(v + 1);
    }
    a.push(vec![v + 1; m]);

    Some((v + 1, a))
}

fn get_t(n: usize, m: usize) -> Option<(usize, Vec<Vec<usize>>)> {
    if n > m {
        return get_t(m, n).map(|(k, ret)| (k, transpose(ret)));
    }

    if n <= 2 {
        return None;
    }

    if n == 3 {
        if m < 6 {
            return None;
        }
        return Some((
            4,
            vec![
                once(1)
                    .chain(repeat(2).take(m - 2))
                    .chain(once(4))
                    .collect(),
                repeat(1)
                    .take(m - 4)
                    .chain(once(2))
                    .chain(once(3))
                    .chain(repeat(4).take(2))
                    .collect(),
                once(1)
                    .chain(repeat(3).take(m - 2))
                    .chain(once(4))
                    .collect(),
            ],
        ));
    }

    if n == 4 {
        return Some((
            4,
            vec![
                repeat(1).take(m - 1).chain(once(2)).collect(),
                once(3)
                    .chain(once(1))
                    .chain(repeat(2).take(m - 2))
                    .collect(),
                repeat(3)
                    .take(m - 2)
                    .chain(once(4))
                    .chain(once(2))
                    .collect(),
                once(3).chain(repeat(4).take(m - 1)).collect(),
            ],
        ));
    }

    if n == 5 {
        return Some((
            5,
            vec![
                repeat(1).take(m - 1).chain(once(4)).collect(),
                once(2)
                    .chain(once(1))
                    .chain(repeat(4).take(m - 2))
                    .collect(),
                repeat(2)
                    .take(m - 2)
                    .chain(once(5))
                    .chain(once(4))
                    .collect(),
                once(2)
                    .chain(once(3))
                    .chain(repeat(5).take(m - 3))
                    .chain(once(4))
                    .collect(),
                repeat(3)
                    .take(m - 2)
                    .chain(once(5))
                    .chain(once(4))
                    .collect(),
            ],
        ));
    }

    let a1 = get_t(n - 3, m).unwrap();
    let a2 = get_t(3, m).unwrap();
    Some(merge_vert(a1, a2))
}

fn get_ct(n: usize, m: usize) -> Option<(usize, Vec<Vec<usize>>)> {
    if n > m {
        return get_ct(m, n).map(|(k, ret)| (k, transpose(ret)));
    }

    if n <= 2 {
        return None;
    }

    if n == 3 {
        return Some((
            2,
            vec![
                repeat(1).take(m - 1).chain(once(2)).collect(),
                once(1).chain(repeat(2).take(m - 1)).collect(),
                repeat(1).take(m - 1).chain(once(2)).collect(),
            ],
        ));
    }

    if n == 4 {
        return Some((
            3,
            vec![
                vec![3; m],
                repeat(1)
                    .take(m - 2)
                    .chain(once(3))
                    .chain(once(2))
                    .collect(),
                once(1).chain(repeat(2).take(m - 1)).collect(),
                repeat(1).take(m - 1).chain(once(2)).collect(),
            ],
        ));
    }

    if n == 5 {
        return Some((
            4,
            vec![
                vec![3; m],
                repeat(1)
                    .take(m - 2)
                    .chain(once(3))
                    .chain(once(2))
                    .collect(),
                once(1).chain(repeat(2).take(m - 1)).collect(),
                repeat(1)
                    .take(m - 2)
                    .chain(once(4))
                    .chain(once(2))
                    .collect(),
                vec![4; m],
            ],
        ));
    }

    let a1 = get_ct(n - 3, m).unwrap();
    let a2 = get_ct(3, m).unwrap();
    Some(merge_vert(a1, a2))
}

fn main() {
    let [h, w] = read_tuple::<usize, 2>();

    for f in [get_c, get_t, get_ct] {
        if let Some((k, ret)) = f(h, w) {
            println!("{}", k);
            for r in ret {
                for c in r {
                    print!("{} ", c);
                }
                println!();
            }
        } else {
            println!("-1");
        }
    }
}

mod fio {
    use std::{
        cell::RefCell,
        convert::TryInto,
        fmt::Debug,
        io::{BufRead, BufWriter, StdinLock, StdoutLock, stdin, stdout},
        str::FromStr,
    };
    thread_local! {
        pub static STDIN: RefCell<StdinLock<'static>> = RefCell::new(stdin().lock());
        pub static STDOUT: RefCell<BufWriter<StdoutLock<'static>>> = RefCell::new(BufWriter::new(stdout().lock()));
    }

    #[allow(dead_code)]
    pub fn read<T: FromStr>() -> T
    where
        <T as FromStr>::Err: Debug,
    {
        read_line().parse().unwrap()
    }

    #[allow(dead_code)]
    pub fn read_vec<T: FromStr>() -> Vec<T>
    where
        <T as FromStr>::Err: Debug,
    {
        read_line()
            .split_whitespace()
            .map(|x| x.parse().unwrap())
            .collect()
    }

    #[allow(dead_code)]
    pub fn read_tuple<T, const N: usize>() -> [T; N]
    where
        T: FromStr + Debug,
        <T as FromStr>::Err: Debug,
    {
        read_vec::<T>().try_into().unwrap()
    }

    /// whitespace at the end of the line is ignored
    pub fn read_line() -> String {
        let mut s = String::new();
        STDIN.with(|cell| {
            cell.borrow_mut().read_line(&mut s).unwrap();
        });
        String::from_str(s.trim_end()).unwrap()
    }
}

#[macro_export]
macro_rules! print {
    ($($t:tt)*) => {
        fio::STDOUT.with(|cell|{
            use std::io::Write;
            write!(cell.borrow_mut(), $($t)*).unwrap()
        })};
}

#[macro_export]
macro_rules! println {
    ($($t:tt)*) => {
        fio::STDOUT.with(|cell| {
            use std::io::Write;
            writeln!(cell.borrow_mut(), $($t)*).unwrap()
        })
    };
}

#[macro_export]
macro_rules! flush {
    () => {
        fio::STDOUT.with(|cell| {
            use std::io::Write;
            cell.borrow_mut().flush().unwrap()
        });
    };
}
0