結果

問題 No.1265 Balloon Survival
ユーザー StrorkisStrorkis
提出日時 2020-10-23 22:47:01
言語 Rust
(1.77.0)
結果
AC  
実行時間 228 ms / 2,000 ms
コード長 2,470 bytes
コンパイル時間 3,524 ms
コンパイル使用メモリ 155,200 KB
実行使用メモリ 14,012 KB
最終ジャッジ日時 2023-09-28 17:07:17
合計ジャッジ時間 7,436 ms
ジャッジサーバーID
（参考情報） 		judge12 / judge11
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1 ms
4,376 KB
testcase_01 AC 1 ms
4,376 KB
testcase_02 AC 1 ms
4,380 KB
testcase_03 AC 1 ms
4,376 KB
testcase_04 AC 1 ms
4,376 KB
testcase_05 AC 1 ms
4,380 KB
testcase_06 AC 1 ms
4,376 KB
testcase_07 AC 1 ms
4,380 KB
testcase_08 AC 1 ms
4,376 KB
testcase_09 AC 1 ms
4,380 KB
testcase_10 AC 1 ms
4,376 KB
testcase_11 AC 1 ms
4,376 KB
testcase_12 AC 1 ms
4,376 KB
testcase_13 AC 2 ms
4,376 KB
testcase_14 AC 10 ms
4,380 KB
testcase_15 AC 8 ms
4,380 KB
testcase_16 AC 3 ms
4,380 KB
testcase_17 AC 76 ms
8,340 KB
testcase_18 AC 4 ms
4,380 KB
testcase_19 AC 3 ms
4,376 KB
testcase_20 AC 10 ms
4,376 KB
testcase_21 AC 27 ms
4,988 KB
testcase_22 AC 14 ms
4,376 KB
testcase_23 AC 16 ms
4,376 KB
testcase_24 AC 206 ms
13,740 KB
testcase_25 AC 205 ms
13,696 KB
testcase_26 AC 200 ms
13,664 KB
testcase_27 AC 201 ms
13,724 KB
testcase_28 AC 211 ms
13,768 KB
testcase_29 AC 198 ms
13,760 KB
testcase_30 AC 203 ms
13,736 KB
testcase_31 AC 220 ms
13,732 KB
testcase_32 AC 219 ms
14,012 KB
testcase_33 AC 228 ms
13,720 KB
testcase_34 AC 1 ms
4,376 KB
testcase_35 AC 1 ms
4,380 KB
権限があれば一括ダウンロードができます

ソースコード

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