結果
| 問題 |
No.2696 Sign Creation
|
| コンテスト | |
| ユーザー |
 naut3
|
| 提出日時 | 2024-03-22 22:53:27 |
| 言語 | Rust (1.83.0 + proconio) |
| 結果 |
WA
|
| 実行時間 | - |
| コード長 | 8,774 bytes |
| コンパイル時間 | 16,062 ms |
| コンパイル使用メモリ | 387,884 KB |
| 実行使用メモリ | 64,804 KB |
| 最終ジャッジ日時 | 2024-12-20 12:19:37 |
| 合計ジャッジ時間 | 23,577 ms |
|
ジャッジサーバーID （参考情報） |
judge1 / judge3 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 3 |
| other | AC * 30 WA * 7 TLE * 1 |
コンパイルメッセージ
warning: value assigned to `ans_now` is never read
--> src/main.rs:129:33
|
129 | let mut ans_now = original_ans;
| ^^^^^^^
|
= help: maybe it is overwritten before being read?
= note: `#[warn(unused_assignments)]` on by default
warning: value assigned to `ans_now` is never read
--> src/main.rs:190:33
|
190 | let mut ans_now = original_ans;
| ^^^^^^^
|
= help: maybe it is overwritten before being read?
ソースコード
#![allow(non_snake_case, unused_imports, unused_must_use)]
use std::io::{self, prelude::*};
use std::str;
fn main() {
let (stdin, stdout) = (io::stdin(), io::stdout());
let mut scan = Scanner::new(stdin.lock());
let mut out = io::BufWriter::new(stdout.lock());
macro_rules! input {
($T: ty) => {
scan.token::<$T>()
};
($T: ty, $N: expr) => {
(0..$N).map(|_| scan.token::<$T>()).collect::<Vec<_>>()
};
}
let H = input!(isize);
let W = input!(isize);
let N = input!(usize);
let D = input!(isize);
let dist = |y1: isize, x1: isize, y2: isize, x2: isize| (y1 - y2).abs() + (x1 - x2).abs();
let mut points = vec![];
let mut has_star = vec![vec![usize::MAX; W as usize + 1]; H as usize + 1];
for i in 0..N {
let (y, x) = (input!(isize), input!(isize));
points.push((y, x));
has_star[y as usize][x as usize] = i;
}
let mut graph = vec![vec![]; N];
for i in 0..N {
let (y, x) = points[i];
for dy in -D..=D {
for dx in -D..=D {
if dist(dy, dx, 0, 0) <= D {
if y + dy >= 1 && y + dy <= H && x + dx >= 1 && x + dx <= W {
if has_star[(y + dy) as usize][(x + dx) as usize] != usize::MAX {
graph[i].push(has_star[(y + dy) as usize][(x + dx) as usize]);
}
}
}
}
}
}
let mut root = (0..N).collect::<Vec<_>>();
let mut seen = vec![false; N];
let mut q = std::collections::VecDeque::default();
for i in 0..N {
if seen[i] {
continue;
}
q.push_front(i);
seen[i] = true;
while let Some(now) = q.pop_front() {
for &nxt in graph[now].iter() {
if seen[nxt] {
continue;
}
seen[nxt] = true;
root[nxt] = i;
q.push_back(nxt);
}
}
}
let mut original_ans = 0;
let mut cnt = vec![0; N];
for &r in root.iter() {
cnt[r] += 1;
}
for i in 0..N {
if cnt[i] >= 2 {
original_ans += 1;
}
}
let mut ans_max = usize::MIN;
let mut ans_min = usize::MAX;
let mut unbound_count = 0;
for i in 0..N {
let (y, x) = points[i];
for dy in -D..=D {
for dx in -D..=D {
if dist(dy, dx, 0, 0) <= D {
if y + dy >= 1 && y + dy <= H && x + dx >= 1 && x + dx <= W {
// put star (y + dy, x + dx)
let mut roots = std::collections::BTreeSet::new();
for dy2 in -D..=D {
for dx2 in -D..=D {
if dist(dy2, dx2, 0, 0) <= D {
if y + dy + dy2 >= 1
&& y + dy + dy2 <= H
&& x + dx + dx2 >= 1
&& x + dx + dx2 <= W
{
if has_star[(y + dy + dy2) as usize]
[(x + dx + dx2) as usize]
!= usize::MAX
{
roots.insert(
root[has_star[(y + dy + dy2) as usize]
[(x + dx + dx2) as usize]],
);
}
}
}
}
}
let mut ans_now = original_ans;
let mut root_cnt = 0;
let mut alone_cnt = 0;
for &r in roots.iter() {
if cnt[r] >= 2 {
root_cnt += 1;
} else if cnt[r] == 1 {
alone_cnt += 1;
}
}
if alone_cnt >= 1 && roots.len() == alone_cnt {
// 孤立した星とだけ接続した場合
ans_now = original_ans + 1;
} else if root_cnt == 0 && alone_cnt == 0 {
// 何も接続しない場合
ans_now = original_ans;
} else {
// すでに星座をなす星と接続した場合
ans_now = original_ans + 1 - root_cnt;
}
ans_max = std::cmp::max(ans_max, ans_now);
ans_min = std::cmp::min(ans_min, ans_now);
}
} else if unbound_count <= 100
&& y + dy >= 1
&& y + dy <= H
&& x + dx >= 1
&& x + dx <= W
{
unbound_count += 1;
if y + dy >= 1 && y + dy <= H && x + dx >= 1 && x + dx <= W {
// put star (y + dy, x + dx)
let mut roots = std::collections::BTreeSet::new();
for dy2 in -D..=D {
for dx2 in -D..=D {
if dist(dy2, dx2, 0, 0) <= D {
if y + dy + dy2 >= 1
&& y + dy + dy2 <= H
&& x + dx + dx2 >= 1
&& x + dx + dx2 <= W
{
if has_star[(y + dy + dy2) as usize]
[(x + dx + dx2) as usize]
!= usize::MAX
{
roots.insert(
root[has_star[(y + dy + dy2) as usize]
[(x + dx + dx2) as usize]],
);
}
}
}
}
}
let mut ans_now = original_ans;
let mut root_cnt = 0;
let mut alone_cnt = 0;
for &r in roots.iter() {
if cnt[r] >= 2 {
root_cnt += 1;
} else if cnt[r] == 1 {
alone_cnt += 1;
}
}
if alone_cnt >= 1 && roots.len() == alone_cnt {
// 孤立した星とだけ接続した場合
ans_now = original_ans + 1;
} else if root_cnt == 0 && alone_cnt == 0 {
// 何も接続しない場合
ans_now = original_ans;
} else {
// すでに星座をなす星と接続した場合
ans_now = original_ans + 1 - root_cnt;
}
ans_max = std::cmp::max(ans_max, ans_now);
ans_min = std::cmp::min(ans_min, ans_now);
}
}
}
}
}
writeln!(out, "{} {}", ans_min, ans_max);
}
struct Scanner<R> {
reader: R,
buf_str: Vec<u8>,
buf_iter: str::SplitWhitespace<'static>,
}
impl<R: BufRead> Scanner<R> {
fn new(reader: R) -> Self {
Self {
reader,
buf_str: vec![],
buf_iter: "".split_whitespace(),
}
}
fn token<T: str::FromStr>(&mut self) -> T {
loop {
if let Some(token) = self.buf_iter.next() {
return token.parse().ok().expect("Failed parse");
}
self.buf_str.clear();
self.reader
.read_until(b'\n', &mut self.buf_str)
.expect("Failed read");
self.buf_iter = unsafe {
let slice = str::from_utf8_unchecked(&self.buf_str);
std::mem::transmute(slice.split_whitespace())
}
}
}
}