結果

問題 No.3335 ReCT
コンテスト
ユーザー akakimidori
提出日時 2025-11-07 23:41:39
言語 Rust
(1.83.0 + proconio)
結果
AC  
実行時間 8 ms / 2,000 ms
コード長 10,478 bytes
コンパイル時間 11,399 ms
コンパイル使用メモリ 398,316 KB
実行使用メモリ 7,720 KB
最終ジャッジ日時 2025-11-07 23:41:58
合計ジャッジ時間 16,492 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 97
権限があれば一括ダウンロードができます
コンパイルメッセージ
warning: unused import: `std::io::Write`
 --> src/main.rs:7:5
  |
7 | use std::io::Write;
  |     ^^^^^^^^^^^^^^
  |
  = note: `#[warn(unused_imports)]` on by default

warning: type alias `Map` is never used
  --> src/main.rs:10:6
   |
10 | type Map<K, V> = BTreeMap<K, V>;
   |      ^^^
   |
   = note: `#[warn(dead_code)]` on by default

warning: type alias `Set` is never used
  --> src/main.rs:11:6
   |
11 | type Set<T> = BTreeSet<T>;
   |      ^^^

warning: type alias `Deque` is never used
  --> src/main.rs:12:6
   |
12 | type Deque<T> = VecDeque<T>;
   |      ^^^^^

ソースコード

diff # 

// 1WA
//
// なんだ？
// 4*4が怪しい？
//

use std::io::Write;
use std::collections::*;

type Map<K, V> = BTreeMap<K, V>;
type Set<T> = BTreeSet<T>;
type Deque<T> = VecDeque<T>;

fn main() {
    input! {
        h: usize,
        w: usize,
    }
    for f in [solve_c, solve_t, solve_tc].iter() {
        let a = (*f)(h, w);
        if let Some(a) = a {
            let v = *a.iter().flatten().max().unwrap();
            println!("{}", v);
            for a in a {
                use util::*;
                println!("{}", a.iter().join(" "));
            }
        } else {
            println!("-1");
        }
    }
    /*
    for h in 2..11 {
        for w in 2..11 {
            println!("h, w = {h} {w}");
            if let Some(a) = solve_t(h, w) {
                for a in a.iter() {
                    for a in a.iter() {
                        print!("{:3}", *a);
                    }
                    println!();
                }
            } else {
                println!("None");
            }
        }
    }
    */
}

// TC
// 3*3可能
// 3*w 可能
// 4*5 可能
// 4*w(>=5) 可能
// 4*4 無理そう
// 5*5 Cおけば3*4にできて、可能
// 6*6
fn solve_tc(mut h: usize, mut w: usize) -> Option<Vec<Vec<i32>>> {
    let trans = h > w;
    if trans {
        std::mem::swap(&mut h, &mut w);
    }
    if h <= 2 {
        return None;
    }
    if (h, w) == (4, 4) {
        let mut ans = vec![vec![0; 4]; 4];
        ans[0] = vec![1, 1, 1, 1];
        ans[1] = vec![2, 1, 3, 3];
        ans[2] = vec![2, 2, 2, 3];
        ans[3] = vec![2, 3, 3, 3];
        return Some(ans);
    }
    let mut k = 1;
    let mut gen = || {
        let r = k;
        k += 1;
        r
    };
    let mut a = vec![vec![0; w]; h];
    let mut ox = 0;
    while h >= 6 {
        let x = gen();
        let y = gen();
        for i in 0..w {
            a[h - 3][i] = x;
            a[h - 2][i] = y;
            a[h - 1][i] = x;
        }
        a[h - 2][0] = x;
        a[h - 1][w - 1] = y;
        a[h - 3][w - 1] = y;
        h -= 3;
    }
    if h == 5 {
        let c = gen();
        for i in 0..w {
            a[0][i] = c;
            a[h - 1][i] = c;
        }
        for i in 0..h {
            a[i][w - 1] = c;
        }
        ox += 1;
        h -= 2;
        w -= 1;
    }
    if h == 3 {
        let x = gen();
        let y = gen();
        for i in 0..w {
            a[ox][i] = x;
            a[ox + 1][i] = y;
            a[ox + 2][i] = x;
        }
        a[ox + 1][0] = x;
        a[ox][w - 1] = y;
        a[ox + 2][w - 1] = y;
    } else {
        let x = gen();
        let y = gen();
        let z = gen();
        for i in 1..w {
            a[ox][i] = x;
            a[ox + 1][i] = y;
            a[ox + 2][i] = z;
            a[ox + 3][i] = x;
        }
        let p = gen();
        for i in 0..4 {
            a[ox + i][0] = x;
            a[ox + i][w - 1] = p;
        }
        a[ox][w - 2] = p;
        a[ox + 3][w - 2] = p;
        a[ox][w - 3] = y;
        a[ox + 3][w - 3] = z;
    }
    if trans {
        a = transpose(a);
    }
    Some(a)
}

// T形
// 3*?
// 3*6は可能
// 引き伸ばせる
// min=3, max>=6 は可能
// 4*4は可能
// 引き伸ばせる
// min=4は可能
// min=5?
// 5*5 できる
// 引き伸ばせる
// 5*w 可能
// 6*6
// 4*4に帰着可能
// 6*w 可能
fn solve_t(mut h: usize, mut w: usize) -> Option<Vec<Vec<i32>>> {
    let trans = h > w;
    if trans {
        std::mem::swap(&mut h, &mut w);
    }
    if h <= 2 || (h == 3 && w < 6) {
        return None;
    }
    let mut k = 1;
    let mut gen = || {
        let r = k;
        k += 1;
        r
    };
    let mut ox = 0;
    let mut a = vec![vec![0; w]; h];
    while h >= 6 {
        let p = gen();
        let q = gen();
        let r = gen();
        for i in 0..w {
            a[ox][i] = p;
            a[ox + h - 1][i] = r;
        }
        for i in 1..(h - 1) {
            a[ox + i][w - 1] = q;
            if i == 2 {
                a[ox + i][w - 2] = q;
            } else if i == 1 {
                a[ox + i][w - 2] = p;
            } else {
                a[ox + i][w - 2] = r;
            }
        }
        ox += 1;
        h -= 2;
        w -= 2;
    }
    if h == 3 {
        if w < 6 {
            return None;
        }
        let p = gen();
        let q = gen();
        let r = gen();
        let s = gen();
        for i in 0..w {
            a[ox][i] = if i == 0 {p} else if i == w - 1 {q} else {r};
            a[ox + 1][i] = if i <= 1 {p} else if i == 2 {r} else if i == 3 {s} else {q};
            a[ox + 2][i] = if i == 0 {p} else if i == w - 1 {q} else {s};
        }
    } else if h == 4 {
        let p = gen();
        let q = gen();
        let r = gen();
        let s = gen();
        for i in 0..w {
            a[ox][i] = p;
            a[ox + 1][i] = q;
            a[ox + 2][i] = r;
            a[ox + 3][i] = s;
        }
        for i in 0..3 {
            a[ox + i][0] = q;
            a[ox + 1 + i][w - 1] = r;
        }
        a[ox + 2][1] = s;
        a[ox + 1][w - 2] = p;
    } else {
        let mut k = [0; 5];
        for i in 0..5 {
            k[i] = gen();
        }
        for i in 0..w {
            for j in 0..5 {
                a[ox + j][i] = k[j];
            }
        }
        a[ox + 1][0] = k[2];
        a[ox + 1][1] = k[0];
        a[ox + 3][0] = k[2];
        a[ox + 3][1] = k[4];
        a[ox + 2][w - 2] = k[3];
        a[ox + 2][w - 1] = k[1];
        a[ox][w - 1] = k[1];
    }
    if trans {
        a = transpose(a);
    }
    Some(a)
}

// C形
// コの組み合わせで3*4 は可能
// 3*3 は無理そう
// 3*5?
// 無理そう
// 3*6
// 可能
// 3*(4以上の偶数) は可能
// 4*4 可能
// 4*w 可能
// 5*5 可能
// 5*w 可能
fn solve_c(mut h: usize, mut w: usize) -> Option<Vec<Vec<i32>>> {
    let trans = h > w;
    if h > w {
        std::mem::swap(&mut h, &mut w);
    }
    if h <= 2 || (h == 3 && w % 2 == 1) {
        return None;
    }
    let mut k = 1;
    let mut gen = || {
        let r = k;
        k += 1;
        r
    };
    let mut ox = 0;
    let mut oy = 0;
    let mut a = vec![vec![0; w]; h];
    while h > 5 || (h == 5 && w % 2 == 1) {
        let k = gen();
        for i in 0..w {
            a[ox][oy + i] = k;
            a[ox + h - 1][oy + i] = k;
        }
        for i in 0..h {
            a[ox + i][oy] = k;
        }
        ox += 1;
        oy += 1;
        h -= 2;
        w -= 1;
    }
    if h == 5 {
        let k = gen();
        for i in 0..w {
            a[ox][oy + i] = k;
        }
        for i in 0..h {
            a[ox + i][oy] = k;
            a[ox + i][oy + w - 1] = k;
        }
        h -= 1;
        w -= 2;
        ox += 1;
        oy += 1;
    }
    if h == 3 {
        let k = gen();
        let mut p = [(0, 0), (1, 0), (2, 0), (2, 1), (2, 2), (1, 2)];
        let b = &mut a;
        let mut a = vec![vec![0; w]; h];
        for &(x, y) in p.iter() {
            a[x][y] = k;
        }
        let mut i = 1;
        while i + 4 < w {
            let d = if i % 4 == 1 {0} else {2};
            let k = gen();
            a[1][i] = k;
            a[d][i] = k;
            a[d][i + 1] = k;
            a[d][i + 2] = k;
            a[d][i + 3] = k;
            a[1][i + 3] = k;
            i += 2;
        }
        for p in p.iter_mut() {
            p.1 = w - 1 - p.1;
            if i % 4 == 1 {
                p.0 = h - 1 - p.0;
            }
        }
        let k = gen();
        for &(x, y) in p.iter() {
            a[x][y] = k;
        }
        for i in 0..h {
            for j in 0..w {
                b[ox + i][oy + j] = a[i][j];
            }
        }
    } else {
        let x = gen();
        let y = gen();
        for i in 0..w {
            a[ox][oy + i] = x;
            a[ox + 1][oy + i] = if i == 0 {x} else {y};
            a[ox + 2][oy + i] = if i == w - 1 {y} else {x};
            a[ox + 3][oy + i] = y;
        }
    }
    if trans {
        a = transpose(a);
    }
    Some(a)
}

// ---------- begin input macro ----------
// reference: https://qiita.com/tanakh/items/0ba42c7ca36cd29d0ac8
#[macro_export]
macro_rules! input {
    (source = $s:expr, $($r:tt)*) => {
        let mut iter = $s.split_whitespace();
        input_inner!{iter, $($r)*}
    };
    ($($r:tt)*) => {
        let s = {
            use std::io::Read;
            let mut s = String::new();
            std::io::stdin().read_to_string(&mut s).unwrap();
            s
        };
        let mut iter = s.split_whitespace();
        input_inner!{iter, $($r)*}
    };
}

#[macro_export]
macro_rules! input_inner {
    ($iter:expr) => {};
    ($iter:expr, ) => {};
    ($iter:expr, $var:ident : $t:tt $($r:tt)*) => {
        let $var = read_value!($iter, $t);
        input_inner!{$iter $($r)*}
    };
}

#[macro_export]
macro_rules! read_value {
    ($iter:expr, ( $($t:tt),* )) => {
        ( $(read_value!($iter, $t)),* )
    };
    ($iter:expr, [ $t:tt ; $len:expr ]) => {
        (0..$len).map(|_| read_value!($iter, $t)).collect::<Vec<_>>()
    };
    ($iter:expr, chars) => {
        read_value!($iter, String).chars().collect::<Vec<char>>()
    };
    ($iter:expr, bytes) => {
        read_value!($iter, String).bytes().collect::<Vec<u8>>()
    };
    ($iter:expr, usize1) => {
        read_value!($iter, usize) - 1
    };
    ($iter:expr, $t:ty) => {
        $iter.next().unwrap().parse::<$t>().expect("Parse error")
    };
}
// ---------- end input macro ----------
mod util {
    pub trait Join {
        fn join(self, sep: &str) -> String;
    }

    impl<T, I> Join for I
    where
        I: Iterator<Item = T>,
        T: std::fmt::Display,
    {
        fn join(self, sep: &str) -> String {
            let mut s = String::new();
            use std::fmt::*;
            for (i, v) in self.enumerate() {
                if i > 0 {
                    write!(&mut s, "{}", sep).ok();
                }
                write!(&mut s, "{}", v).ok();
            }
            s
        }
    }
}
// ---------- begin transpose ----------
pub fn transpose<T>(a: Vec<Vec<T>>) -> Vec<Vec<T>> {
    if a.is_empty() {
        return a;
    }
    let h = a.len();
    let w = a[0].len();
    assert!(a.iter().all(|a| a.len() == w));
    let mut ta: Vec<_> = (0..w).map(|_| Vec::with_capacity(h)).collect();
    for a in a {
        for (ta, a) in ta.iter_mut().zip(a) {
            ta.push(a);
        }
    }
    ta
}
// ---------- end transpose ----------
0