Submission #26487500

---

Source Code Expand

#![allow(non_snake_case, unused)]

use proconio::{*, marker::*};
use rand::prelude::*;
use std::collections::BinaryHeap;

pub trait SetMinMax {
	fn setmin(&mut self, v: Self) -> bool;
	fn setmax(&mut self, v: Self) -> bool;
}
impl<T> SetMinMax for T where T: PartialOrd {
	fn setmin(&mut self, v: T) -> bool {
		*self > v && { *self = v; true }
	}
	fn setmax(&mut self, v: T) -> bool {
		*self < v && { *self = v; true }
	}
}

#[macro_export]
macro_rules! mat {
	($($e:expr),*) => { Vec::from(vec![$($e),*]) };
	($($e:expr,)*) => { Vec::from(vec![$($e),*]) };
	($e:expr; $d:expr) => { Vec::from(vec![$e; $d]) };
	($e:expr; $d:expr $(; $ds:expr)+) => { Vec::from(vec![mat![$e $(; $ds)*]; $d]) };
}

pub fn get_time() -> f64 {
	static mut STIME: f64 = -1.0;
	let t = std::time::SystemTime::now().duration_since(std::time::UNIX_EPOCH).unwrap();
	let ms = t.as_secs() as f64 + t.subsec_nanos() as f64 * 1e-9;
	unsafe {
		if STIME < 0.0 {
			STIME = ms;
		}
		ms - STIME
	}
}

use std::cell::Cell;

#[derive(Clone, Debug)]
pub struct UnionFind {
	/// size / parent
	ps: Vec<Cell<usize>>,
	pub is_root: Vec<bool>
}

impl UnionFind {
	pub fn new(n: usize) -> UnionFind {
		UnionFind { ps: vec![Cell::new(1); n], is_root: vec![true; n] }
	}
	pub fn find(&self, x: usize) -> usize {
		if self.is_root[x] { x }
		else {
			let p = self.find(self.ps[x].get());
			self.ps[x].set(p);
			p
		}
	}
	pub fn unite(&mut self, x: usize, y: usize) {
		let mut x = self.find(x);
		let mut y = self.find(y);
		if x == y { return }
		if self.ps[x].get() < self.ps[y].get() {
			::std::mem::swap(&mut x, &mut y);
		}
		*self.ps[x].get_mut() += self.ps[y].get();
		self.ps[y].set(x);
		self.is_root[y] = false;
	}
	pub fn same(&self, x: usize, y: usize) -> bool {
		self.find(x) == self.find(y)
	}
	pub fn size(&self, x: usize) -> usize {
		self.ps[self.find(x)].get()
	}
}

pub const DIJ: [(usize, usize); 4] = [(!0, 0), (0, !0), (0, 1), (1, 0)];

pub type Output = Vec<(usize, usize, usize)>;

pub struct Input {
	pub N: usize,
	pub K: usize,
	pub B: usize,
	pub ps: Vec<(usize, usize)>,
	pub C: Vec<i64>,
	pub s: Vec<Vec<Vec<char>>>
}

fn read_input() -> Input {
	input! {
		N: usize,
		K: usize,
		B: usize,
		ps: [(usize, usize); K]
	}
	let mut C = vec![];
	let mut s = vec![];
	for _ in 0..B {
		input! {
			n: usize,
			_m: usize,
			Ci: i64,
			si: [Chars; n]
		}
		C.push(Ci);
		s.push(si);
	}
	Input { N, K, B, ps, C, s }
}

fn write_output(out: &Output) {
	println!("{}", out.len());
	for &(b, i, j) in out {
		println!("{} {} {}", b + 1, i, j);
	}
}

const INF: i64 = 100000000;
const TL: f64 = 1.95;

fn can_place(input: &Input, used: &Vec<Vec<bool>>, b: usize, x: usize, y: usize) -> bool {
	if x + input.s[b].len() > input.N || y + input.s[b][0].len() > input.N {
		return false;
	}
	for i in 0..input.s[b].len() {
		for j in 0..input.s[b][0].len() {
			if input.s[b][i][j] == '#' {
				if used[x + i][y + j] {
					return false;
				}
			}
		}
	}
	true
}

fn get_used(input: &Input, out: &Output) -> Vec<Vec<bool>> {
	let mut used = mat![false; input.N; input.N];
	for &(b, i, j) in out {
		for x in 0..input.s[b].len() {
			for y in 0..input.s[b][0].len() {
				if input.s[b][x][y] == '#' {
					let i = i + x;
					let j = j + y;
					used[i][j] = true;
				}
			}
		}
	}
	used
}


#[derive(Clone, Debug)]
enum Ret {
	Out(Output),
	Failed,
	Continue,
}

fn reconnect(input: &Input, adj: &Vec<Vec<Vec<(usize, usize)>>>, out: &Output, mut ub: usize, deleted: &Output, rng: &mut SmallRng) -> Ret {
	let mut uf = UnionFind::new(input.N * input.N);
	let mut used = get_used(input, out);
	for i in 0..input.N {
		for j in 0..input.N {
			if used[i][j] {
				if i + 1 < input.N && used[i + 1][j] {
					uf.unite(i * input.N + j, (i + 1) * input.N + j);
				}
				if j + 1 < input.N && used[i][j + 1] {
					uf.unite(i * input.N + j, i * input.N + j + 1);
				}
			}
		}
	}
	let mut cs = vec![];
	for i in 0..input.K {
		cs.push(uf.find(input.ps[i].0 * input.N + input.ps[i].1));
	}
	cs.sort();
	cs.dedup();
	if cs.len() > ub {
		return Ret::Continue;
	}
	if ub == input.K {
		ub = cs.len().max(rng.gen_range(3, if input.K <= 10 { 5 } else { 7 }));
	}
	let mut del = get_used(&input, &deleted);
	let mut cand = vec![];
	for k in 0..out.len() {
		let (b, i, j) = out[k];
		let mut ok = false;
		for x in 0..input.s[b].len() {
			for y in 0..input.s[b][0].len() {
				if input.s[b][x][y] == '#' {
					let i = i + x;
					let j = j + y;
					for &(di, dj) in &DIJ {
						let i2 = i + di;
						let j2 = j + dj;
						if i2 < input.N && j2 < input.N && del[i2][j2] {
							ok = true;
						}
					}
				}
			}
		}
		if ok {
			cand.push(k);
		}
	}
	cand.shuffle(rng);
	for k in cand {
		let mut deleted2 = deleted.clone();
		let mut out2 = out.clone();
		deleted2.push(out2.remove(k));
		match reconnect(input, adj, &out2, ub, &deleted2, rng) {
			Ret::Continue => continue,
			r => return r
		}
	}
	let n = cs.len();
	let mut toc = vec![!0; input.N * input.N];
	for i in 0..n {
		toc[cs[i]] = i;
	}
	let mut dp = mat![INF; n; input.B; input.N; input.N];
	let mut prev = mat![(!0, !0, !0); n; input.B; input.N; input.N];
	let mut que = BinaryHeap::new();
	for &(b, i, j) in out {
		let c = toc[uf.find(i * input.N + j + input.s[b][0].iter().position(|&c| c == '#').unwrap())];
		if c == !0 {
			continue;
		}
		dp[c][b][i][j] = 0;
		que.push((0, c, b, i, j));
	}
	for &(i, j) in &input.ps {
		if !used[i][j] {
			let c = toc[uf.find(i * input.N + j)];
			for b in 0..input.B {
				for &(di, dj) in &adj[input.B][b] {
					let i2 = i + di;
					let j2 = j + dj;
					if i2 < input.N && j2 < input.N && can_place(&input, &used, b, i2, j2) {
						dp[c][b][i2][j2] = input.C[b];
						que.push((-dp[c][b][i2][j2], c, b, i2, j2));
					}
				}
			}
		}
	}
	let mut count = 0;
	let mut best = deleted.iter().map(|&(b, _, _)| input.C[b]).sum::<i64>();
	let mut best_bij = (!0, !0, !0);
	while let Some((d, c, b, i, j)) = que.pop() {
		if get_time() > TL {
			return Ret::Failed;
		}
		let d = -d;
		if d != dp[c][b][i][j] {
			continue;
		}
		if d >= best {
			break;
		}
		if d > 0 {
			if !can_place(input, &used, b, i, j) {
				dp[c][b][i][j] = -1;
				continue;
			}
		}
		if (0..n).all(|k| 0 <= dp[k][b][i][j] && dp[k][b][i][j] < INF) {
			if best.setmin((0..n).map(|k| dp[k][b][i][j] - input.C[b]).sum::<i64>() + input.C[b]) {
				best_bij = (b, i, j);
			}
			count += 1;
			if count >= 100 {
				break;
			}
		}
		for b2 in 0..input.B {
			for &(di, dj) in &adj[b][b2] {
				let i2 = i + di;
				let j2 = j + dj;
				if i2 < input.N && j2 < input.N && i2 + input.s[b2].len() <= input.N && j2 + input.s[b2][0].len() <= input.N && dp[c][b2][i2][j2].setmin(d + input.C[b2]) {
					dp[c][b2][i2][j2] = d + input.C[b2];
					prev[c][b2][i2][j2] = (b, i, j);
					que.push((-dp[c][b2][i2][j2], c, b2, i2, j2));
				}
			}
		}
	}
	if best_bij.0 == !0 {
		return Ret::Failed;
	}
	let mut out = out.clone();
	for c in 0..n {
		let (mut b, mut i, mut j) = best_bij;
		let mut first = true;
		while b != !0 && dp[c][b][i][j] > 0 {
			if !first || c == 0 {
				out.push((b, i, j));
				if !can_place(input, &used, b, i, j) {
					eprintln!("orz");
					return Ret::Failed;
				}
				for x in 0..input.s[b].len() {
					for y in 0..input.s[b][0].len() {
						if input.s[b][x][y] == '#' {
							used[i + x][j + y] = true;
						}
					}
				}
			}
			first = false;
			let (b2, i2, j2) = prev[c][b][i][j];
			b = b2;
			i = i2;
			j = j2;
		}
	}
	Ret::Out(out)
}

fn solve(input: &Input) -> Output {
	let mut adj = mat![vec![]; input.B + 1; input.B];
	for b1 in 0..input.B {
		for b2 in 0..input.B {
			for di in -(input.s[b2].len() as i32)..=input.s[b1].len() as i32 {
				'lp: for dj in -(input.s[b2][0].len() as i32)..=input.s[b1][0].len() as i32 {
					let mut ok = false;
					for i in 0..input.s[b2].len() {
						for j in 0..input.s[b2][0].len() {
							if input.s[b2][i][j] == '#' {
								let i2 = i + di as usize;
								let j2 = j + dj as usize;
								if i2 < input.s[b1].len() && j2 < input.s[b1][0].len() && input.s[b1][i2][j2] == '#' {
									continue 'lp;
								}
								for &(di2, dj2) in &DIJ {
									let i3 = i2 + di2;
									let j3 = j2 + dj2;
									if i3 < input.s[b1].len() && j3 < input.s[b1][0].len() && input.s[b1][i3][j3] == '#' {
										ok = true;
									}
								}
							}
						}
					}
					if ok {
						adj[b1][b2].push((di as usize, dj as usize));
					}
				}
			}
		}
	}
	for b in 0..input.B {
		for x in 0..input.s[b].len() {
			for y in 0..input.s[b][0].len() {
				if input.s[b][x][y] == '#' {
					adj[input.B][b].push((0 - x, 0 - y));
				}
			}
		}
	}
	let mut mark = mat![!0; input.N; input.N];
	for k in 0..input.K {
		mark[input.ps[k].0][input.ps[k].1] = k;
	}
	macro_rules! id {
		($p:expr) => {{
			let (i, j) = $p;
			i * input.N + j
		}};
		($i:expr, $j:expr) => {
			$i * input.N + $j
		}
	}
	let mut used = mat![false; input.N; input.N];
	let mut out: Output = vec![];
	let mut uf = UnionFind::new(input.N * input.N);
	loop {
		let mut best = 1e20;
		let mut best_bij = (!0, !0, !0);
		for b in 0..input.B {
			for i in 0..=input.N - input.s[b].len() {
				for j in 0..=input.N - input.s[b][0].len() {
					if can_place(input, &used, b, i, j) {
						let mut tmp = vec![];
						for x in 0..input.s[b].len() {
							for y in 0..input.s[b][0].len() {
								if input.s[b][x][y] == '#' {
									if mark[i + x][j + y] != !0 {
										tmp.push(id!(i + x, j + y));
									}
									for &(di, dj) in &DIJ {
										let i2 = i + x + di;
										let j2 = j + y + dj;
										if i2 < input.N && j2 < input.N && used[i2][j2] {
											tmp.push(uf.find(id!(i2, j2)));
										}
									}
								}
							}
						}
						tmp.sort();
						tmp.dedup();
						if tmp.len() >= 2 && best.setmin(input.C[b] as f64 / (tmp.len() - 1) as f64) {
							best_bij = (b, i, j);
						}
					}
				}
			}
		}
		if best == 1e20 {
			break;
		}
		let (b, i, j) = best_bij;
		out.push((b, i, j));
		for x in 0..input.s[b].len() {
			for y in 0..input.s[b][0].len() {
				if input.s[b][x][y] == '#' {
					used[i + x][j + y] = true;
					for &(di, dj) in &DIJ {
						let i2 = i + x + di;
						let j2 = j + y + dj;
						if i2 < input.N && j2 < input.N && used[i2][j2] {
							uf.unite(id!(i + x, j + y), id!(i2, j2));
						}
					}
				}
			}
		}
	}
	let mut s = 0;
	'lp2: while (0..input.K).any(|i| !used[input.ps[i].0][input.ps[i].1] || !uf.same(id!(input.ps[s]), id!(input.ps[i]))) {
		let mut que = BinaryHeap::new();
		let mut dp = mat![INF; input.B; input.N; input.N];
		let mut prev = mat![(!0, !0, !0); input.B; input.N; input.N];
		if !used[input.ps[s].0][input.ps[s].1] {
			for b in 0..input.B {
				for &(di, dj) in &adj[input.B][b] {
					let i2 = input.ps[s].0 + di;
					let j2 = input.ps[s].1 + dj;
					if i2 < input.N && j2 < input.N && can_place(&input, &used, b, i2, j2) {
						dp[b][i2][j2] = input.C[b];
						que.push((-dp[b][i2][j2], b, i2, j2));
					}
				}
			}
		} else {
			for &(b, i, j) in &out {
				if uf.same(id!(input.ps[s]), id!(i, j + input.s[b][0].iter().position(|&c| c == '#').unwrap())) {
					dp[b][i][j] = 0;
					que.push((0, b, i, j));
				}
			}
		}
		while let Some((d, mut b, mut i, mut j)) = que.pop() {
			let d = -d;
			if d != dp[b][i][j] {
				continue;
			}
			if d > 0 {
				if !can_place(input, &used, b, i, j) {
					dp[b][i][j] = 0;
					continue;
				}
				let mut ok = false;
				for x in 0..input.s[b].len() {
					for y in 0..input.s[b][0].len() {
						if input.s[b][x][y] == '#' {
							if mark[i + x][j + y] != !0 && mark[i + x][j + y] != s {
								ok = true;
							} else {
								for &(di, dj) in &DIJ {
									let i2 = i + x + di;
									let j2 = j + y + dj;
									if i2 < input.N && j2 < input.N && used[i2][j2] && !uf.same(id!(input.ps[s]), id!(i2, j2)) {
										ok = true;
									}
								}
							}
						}
					}
				}
				if ok {
					while b != !0 && dp[b][i][j] > 0 {
						if !can_place(input, &used, b, i, j) {
							eprintln!("orz");
							continue 'lp2;
						}
						out.push((b, i, j));
						for x in 0..input.s[b].len() {
							for y in 0..input.s[b][0].len() {
								if input.s[b][x][y] == '#' {
									used[i + x][j + y] = true;
									for &(di, dj) in &DIJ {
										let i2 = i + x + di;
										let j2 = j + y + dj;
										if i2 < input.N && j2 < input.N && used[i2][j2] {
											uf.unite(id!(i + x, j + y), id!(i2, j2));
										}
									}
								}
							}
						}
						let tmp = prev[b][i][j];
						b = tmp.0;
						i = tmp.1;
						j = tmp.2;
					}
					break;
				}
			}
			for b2 in 0..input.B {
				for &(di, dj) in &adj[b][b2] {
					let i2 = i + di;
					let j2 = j + dj;
					if i2 < input.N && j2 < input.N && i2 + input.s[b2].len() <= input.N && j2 + input.s[b2][0].len() <= input.N && dp[b2][i2][j2].setmin(d + input.C[b2]) {
						dp[b2][i2][j2] = d + input.C[b2];
						prev[b2][i2][j2] = (b, i, j);
						que.push((-dp[b2][i2][j2], b2, i2, j2));
					}
				}
			}
		}
	}
	let mut rng = rand::rngs::SmallRng::seed_from_u64(74893279);
	let mut iter = 0;
	let mut best = compute_cost(&input, &out);
	eprintln!("{:.3}: {}", get_time(), best);
	while get_time() < TL {
		iter += 1;
		let p = rng.gen_range(0, out.len());
		let mut out2 = out.clone();
		let deleted = vec![out2.remove(p)];
		if let Ret::Out(out2) = reconnect(input, &adj, &out2, input.K, &deleted, &mut rng) {
			if best.setmin(compute_cost(&input, &out2)) {
				out = out2;
				eprintln!("{:.3}: {}", get_time(), best);
			}
		}
	}
	eprintln!("Iter = {}", iter);
	out
}

fn compute_cost(input: &Input, out: &Output) -> i64 {
	out.iter().map(|&(b, _, _)| input.C[b]).sum::<i64>()	
}

fn main() {
	get_time();
	let input = read_input();
	let out = solve(&input);
	eprintln!("Time = {:.3}", get_time());
	eprintln!("Score = {}", (1e8 / compute_cost(&input, &out) as f64).round() as i64);
	write_output(&out);
}

Submission Info

Judge Result