結果
| 問題 |
No.3335 ReCT
|
| コンテスト | |
| ユーザー |
 akakimidori
|
| 提出日時 | 2025-11-07 23:40:44 |
| 言語 | Rust (1.83.0 + proconio) |
| 結果 |
WA
|
| 実行時間 | - |
| コード長 | 10,452 bytes |
| コンパイル時間 | 12,848 ms |
| コンパイル使用メモリ | 398,084 KB |
| 実行使用メモリ | 7,720 KB |
| 最終ジャッジ日時 | 2025-11-07 23:41:02 |
| 合計ジャッジ時間 | 15,888 ms |
|
ジャッジサーバーID （参考情報） |
judge2 / judge4 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 2 |
| other | AC * 96 WA * 1 |
コンパイルメッセージ
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>; | ^^^^^
ソースコード
// 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];
}
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 ----------