結果
| 問題 |
No.2641 draw X
|
| コンテスト | |
| ユーザー |
 LyricalMaestro
|
| 提出日時 | 2025-06-29 02:27:03 |
| 言語 | Rust (1.83.0 + proconio) |
| 結果 |
TLE
|
| 実行時間 | - |
| コード長 | 6,526 bytes |
| コンパイル時間 | 15,047 ms |
| コンパイル使用メモリ | 398,696 KB |
| 実行使用メモリ | 109,220 KB |
| 最終ジャッジ日時 | 2025-06-29 02:27:23 |
| 合計ジャッジ時間 | 17,728 ms |
|
ジャッジサーバーID （参考情報） |
judge1 / judge4 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | -- * 3 |
| other | AC * 16 TLE * 1 -- * 24 |
ソースコード
use std::collections::HashMap;
use std::io::{self, BufRead};
fn main() {
// 入力
let stdin = io::stdin();
let mut lines = stdin.lock().lines().map(|l| l.unwrap());
let first = lines.next().unwrap();
let mut first_it = first.split_whitespace();
let h: usize = first_it.next().unwrap().parse().unwrap();
let w: usize = first_it.next().unwrap().parse().unwrap();
let s: Vec<Vec<char>> = lines.take(h).map(|line| line.chars().collect()).collect();
// i_j1, i_j2
let mut i_j1: HashMap<i32, Vec<usize>> = HashMap::new();
let mut i_j2: HashMap<i32, Vec<usize>> = HashMap::new();
for i in 0..h {
for j in 0..w {
let x = i as i32 + j as i32;
let y = i as i32 - j as i32;
i_j1.entry(x).or_default().push(i);
i_j2.entry(y).or_default().push(i);
}
}
// i_j1_cums
let mut i_j1_cums: HashMap<i32, HashMap<usize, i32>> = HashMap::new();
for (&key, values) in &i_j1 {
let mut values = values.clone();
values.sort_unstable();
let mut new_values = Vec::new();
let mut c = 0;
for &i in &values {
let j = (key as isize - i as isize) as usize;
if s[i][j] == '#' {
c += 1;
}
new_values.push(c);
}
let mut value_map = HashMap::new();
for (idx, &v) in new_values.iter().enumerate() {
value_map.insert(values[idx], v);
}
i_j1_cums.insert(key, value_map);
}
// i_j2_cums
let mut i_j2_cums: HashMap<i32, HashMap<usize, i32>> = HashMap::new();
for (&key, values) in &i_j2 {
let mut values = values.clone();
values.sort_unstable();
let mut new_values = Vec::new();
let mut c = 0;
for &i in &values {
let j = (i as isize - key as isize) as usize;
if s[i][j] == '#' {
c += 1;
}
new_values.push(c);
}
let mut value_map = HashMap::new();
for (idx, &v) in new_values.iter().enumerate() {
value_map.insert(values[idx], v);
}
i_j2_cums.insert(key, value_map);
}
// solve関数
fn solve(ar: &HashMap<usize, i32>, i: usize, mid: i32) -> bool {
let high_i = i as i32 + mid;
let low_i = i as i32 - mid;
let high_i_u = high_i as usize;
let low_i_u = low_i as usize;
if !ar.contains_key(&high_i_u) || !ar.contains_key(&low_i_u) {
return false;
}
if !ar.contains_key(&(low_i_u - 1)) {
let x = ar[&high_i_u];
x == 1 + 2 * mid
} else {
let x = ar[&high_i_u];
let x1 = ar[&(low_i_u - 1)];
(x - x1) == 1 + 2 * mid
}
}
let mut i_j1_imos: HashMap<i32, HashMap<usize, i32>> = HashMap::new();
let mut i_j2_imos: HashMap<i32, HashMap<usize, i32>> = HashMap::new();
for i in 0..h {
for j in 0..w {
if s[i][j] != '#' {
continue;
}
let mut is_ok = true;
for (di, dj) in &[(1, 1), (1, -1), (-1, 1), (-1, -1)] {
let new_i = i as isize + di;
let new_j = j as isize + dj;
if new_i < 0 || new_i >= h as isize || new_j < 0 || new_j >= w as isize {
is_ok = false;
break;
}
if s[new_i as usize][new_j as usize] == '.' {
is_ok = false;
break;
}
}
if !is_ok {
continue;
}
// i_j1
let key1 = i as i32 + j as i32;
let ar1 = &i_j1_cums[&key1];
let mut low = 1;
let mut high = h.max(w) as i32;
while high - low > 1 {
let mid = (high + low) / 2;
if solve(ar1, i, mid) {
low = mid;
} else {
high = mid;
}
}
let ij1_val = if solve(ar1, i, high) { high } else { low };
// i_j2
let key2 = i as i32 - j as i32;
let ar2 = &i_j2_cums[&key2];
let mut low = 1;
let mut high = h.max(w) as i32;
while high - low > 1 {
let mid = (high + low) / 2;
if solve(ar2, i, mid) {
low = mid;
} else {
high = mid;
}
}
let ij2_val = if solve(ar2, i, high) { high } else { low };
let ans = ij1_val.min(ij2_val);
// imos
let min_i = i as i32 - ans;
let max_i = i as i32 + ans + 1;
i_j1_imos.entry(key1).or_default().entry(min_i as usize).and_modify(|v| *v += 1).or_insert(1);
i_j1_imos.entry(key1).or_default().entry(max_i as usize).and_modify(|v| *v -= 1).or_insert(-1);
i_j2_imos.entry(key2).or_default().entry(min_i as usize).and_modify(|v| *v += 1).or_insert(1);
i_j2_imos.entry(key2).or_default().entry(max_i as usize).and_modify(|v| *v -= 1).or_insert(-1);
}
}
let mut passed = vec![vec![0i32; w]; h];
for (&key, values_map) in &i_j1_imos {
let min_i = *values_map.keys().min().unwrap();
let max_i = *values_map.keys().max().unwrap();
let mut c = 0;
for i in min_i..max_i {
if let Some(v) = values_map.get(&i) {
c += v;
}
let j0 = (key - i as i32) as usize;
if i < h && j0 < w {
passed[i][j0] += c;
}
}
}
for (&key, values_map) in &i_j2_imos {
let min_i = *values_map.keys().min().unwrap();
let max_i = *values_map.keys().max().unwrap();
let mut c = 0;
for i in min_i..max_i {
if let Some(v) = values_map.get(&i) {
c += v;
}
let j0 = (i as i32 - key) as usize;
if i < h && j0 < w {
passed[i][j0] += c;
}
}
}
let mut is_ok = true;
for i in 0..h {
for j in 0..w {
if passed[i][j] > 0 && s[i][j] == '.' {
is_ok = false;
}
if passed[i][j] == 0 && s[i][j] == '#' {
is_ok = false;
}
}
}
if is_ok {
println!("Yes");
} else {
println!("No");
}
}