結果
問題 | 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)}