結果

問題 No.1265 Balloon Survival
コンテスト
ユーザー Strorkis
提出日時 2020-10-23 22:47:01
言語 Rust
(1.83.0 + proconio)
結果
AC  
実行時間 205 ms / 2,000 ms
コード長 2,470 bytes
コンパイル時間 18,790 ms
コンパイル使用メモリ 378,840 KB
実行使用メモリ 13,824 KB
最終ジャッジ日時 2024-07-21 11:48:38
合計ジャッジ時間 22,980 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 32
権限があれば一括ダウンロードができます

ソースコード

diff # 

use std::io::{self, BufRead, Write};
use std::str::FromStr;

struct Solver<'a> {
    reader: io::BufReader<io::StdinLock<'a>>,
    writer: io::BufWriter<io::StdoutLock<'a>>,
}

impl Solver<'_> {
    fn read_line(&mut self) -> String {
        let mut input = String::new();
        self.reader.read_line(&mut input).unwrap();
        input
    }

    fn read<T: FromStr>(&mut self) -> T {
        let input = self.read_line();
        input.trim_end().parse().ok().unwrap()
    }

    fn read_pair<T1: FromStr, T2: FromStr>(&mut self) -> (T1, T2) {
        let input = self.read_line();
        let mut iter = input.split_whitespace();
        (
            iter.next().unwrap().parse().ok().unwrap(),
            iter.next().unwrap().parse().ok().unwrap(),
        )
    }

    fn read_pair_vec<T1, T2>(&mut self, n: usize) -> (Vec<T1>, Vec<T2>)
        where T1: FromStr, T2: FromStr
    {
        let mut v1 = Vec::with_capacity(n);
        let mut v2 = Vec::with_capacity(n);
        for _ in 0..n {
            let (x1, x2) = self.read_pair();
            v1.push(x1);
            v2.push(x2);
        }
        (v1, v2)
    }

    fn writeln<T: std::fmt::Display>(&mut self, ans: T) {
        writeln!(self.writer, "{}", ans).unwrap();
    }

    fn solve(&mut self) {
        use std::cmp::Reverse;
        use std::collections::BinaryHeap;

        let n = self.read::<usize>();
        let (x, y) = self.read_pair_vec::<i64, i64>(n);

        let mut heap = BinaryHeap::new();
        for i in 0..n {
            for j in (i + 1)..n {
                let d = (x[i] - x[j]).pow(2) + (y[i] - y[j]).pow(2);
                heap.push((Reverse(d), i, j));
            }
        }

        let mut ans = 0;
        let mut check = vec![false; n];
        while let Some((_, i, j)) = heap.pop() {
            if check[i] || check[j] { continue; }
            if i == 0 {
                ans += 1;
                check[j] = true;
            } else if j == 0 {
                ans += 1;
                check[i] = true;
            } else {
                check[i] = true;
                check[j] = true;
            }
        }
        self.writeln(ans);
    }

    fn run() {
        let (stdin, stdout) = (io::stdin(), io::stdout());
        let reader = io::BufReader::new(stdin.lock());
        let writer = io::BufWriter::new(stdout.lock());
        let mut solver = Solver { reader, writer };
        solver.solve();
    }
}

fn main() {
    Solver::run();
}
0