結果
問題 | No.2923 Mayor's Job |
ユーザー |
|
提出日時 | 2024-10-12 16:22:06 |
言語 | Rust (1.83.0 + proconio) |
結果 |
AC
|
実行時間 | 9 ms / 2,000 ms |
コード長 | 1,260 bytes |
コンパイル時間 | 14,432 ms |
コンパイル使用メモリ | 378,820 KB |
実行使用メモリ | 5,248 KB |
最終ジャッジ日時 | 2024-10-12 16:23:12 |
合計ジャッジ時間 | 15,447 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 17 |
ソースコード
use std::collections::BTreeMap; use proconio::input; fn main() { input! { (n, k): (usize, usize), hh: [usize; n], xy: [(usize, usize); n], } let square_k = k.pow(2); let mut coords_per_history: BTreeMap<usize, Vec<(usize, usize)>> = BTreeMap::new(); for (&h, &coord) in hh.iter().zip(&xy) { coords_per_history.entry(h).or_default().push(coord); } let mut num_removed_shrines = 0_usize; let mut candidate_coords: Vec<(usize, usize)> = vec![]; for coords in coords_per_history.into_values() { let check_removable = |low_coord: (usize, usize)| { coords .iter() .any(|&high_coord| calc_square_dist(low_coord, high_coord) <= square_k) }; let prev_num_candidates = candidate_coords.len(); candidate_coords.retain(|&low_coord| !check_removable(low_coord)); num_removed_shrines += prev_num_candidates - candidate_coords.len(); candidate_coords.extend(coords); } println!("{}", n - num_removed_shrines); } fn calc_square_dist(coord1: (usize, usize), coord2: (usize, usize)) -> usize { let (x1, y1) = coord1; let (x2, y2) = coord2; x1.abs_diff(x2).pow(2) + y1.abs_diff(y2).pow(2) }