結果
| 問題 | No.1427 Simplified Tetris |
| コンテスト | |
| ユーザー |
 akakimidori
|
| 提出日時 | 2021-03-13 14:46:09 |
| 言語 | Rust (1.83.0 + proconio) |
| 結果 |
WA
|
| 実行時間 | - |
| コード長 | 8,135 bytes |
| 記録 | |
| コンパイル時間 | 14,004 ms |
| コンパイル使用メモリ | 379,980 KB |
| 実行使用メモリ | 5,248 KB |
| 最終ジャッジ日時 | 2024-10-15 06:19:35 |
| 合計ジャッジ時間 | 16,762 ms |
|
ジャッジサーバーID （参考情報） |
judge5 / judge2 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 4 |
| other | AC * 34 WA * 3 |
ソースコード
// ---------- 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 - 1;
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");
}