#1017977 (Rust) No.2923 Mayor's Job

• 問題: No.2923 Mayor's Job
• ユーザー: ぱるま
• 提出日時: 2024-10-12 15:44:52
• 言語: Rust (1.77.0 + proconio)
• 結果: AC
• 実行時間: 9 ms / 2,000 ms
• コード長: 7,263 bytes
• コンパイル時間: 13,441 ms
• コンパイル使用メモリ: 379,048 KB
• 実行使用メモリ: 5,248 KB
• 最終ジャッジ日時: 2024-10-12 15:46:20
• 合計ジャッジ時間: 14,519 ms
• ジャッジサーバーID （参考情報）: judge4 / judge2

入力	結果	実行時間; 実行使用メモリ
testcase_00	AC	1 ms; 5,248 KB
testcase_01	AC	1 ms; 5,248 KB
testcase_02	AC	1 ms; 5,248 KB
testcase_03	AC	9 ms; 5,248 KB
testcase_04	AC	6 ms; 5,248 KB
testcase_05	AC	6 ms; 5,248 KB
testcase_06	AC	7 ms; 5,248 KB
testcase_07	AC	6 ms; 5,248 KB
testcase_08	AC	6 ms; 5,248 KB
testcase_09	AC	7 ms; 5,248 KB
testcase_10	AC	6 ms; 5,248 KB
testcase_11	AC	7 ms; 5,248 KB
testcase_12	AC	8 ms; 5,248 KB
testcase_13	AC	2 ms; 5,248 KB
testcase_14	AC	1 ms; 5,248 KB
testcase_15	AC	1 ms; 5,248 KB
testcase_16	AC	1 ms; 5,248 KB
testcase_17	AC	1 ms; 5,248 KB
testcase_18	AC	1 ms; 5,248 KB
testcase_19	AC	1 ms; 5,248 KB

コンパイルメッセージ

warning: unused variable: `n`
  --> src/main.rs:44:13
   |
44 |         let n = self.n;
   |             ^ help: if this is intentional, prefix it with an underscore: `_n`
   |
   = note: `#[warn(unused_variables)]` on by default

ソースコード

//#[derive_readable]
#[derive(Clone, Copy, Debug, PartialEq, Eq)]
struct Jinja {
    h: i64,
    pos: Pos<i64>,
}

#[derive(Debug, Clone)]
struct Problem {
    n: usize,
    k: i64,
    jinjas: Vec<Jinja>,
}

fn dist_sq(p1: Pos<i64>, p2: Pos<i64>) -> i64 {
    let d = p2 - p1;
    d.norm_square()
}

impl Problem {
    fn read() -> Problem {
        input! {
            n: usize,
            k: i64,
            hs: [i64; n],
            ps: [(i64, i64); n],
        }
        let ps = ps
            .iter()
            .copied()
            .map(|(x, y)| Pos::new(x, y))
            .collect::<Vec<_>>();

        let jinjas = (0..n)
            .map(|i| Jinja {
                h: hs[i],
                pos: ps[i],
            })
            .collect();
        Problem { n, k, jinjas }
    }

    fn solve(&self) -> Answer {
        let n = self.n;
        let k = self.k;
        let jinjas = {
            let mut t = self.jinjas.clone();
            t.sort_by_key(|j| j.h);
            t
        };

        let ans = jinjas
            .iter()
            .copied()
            .filter(|j1| {
                // j1 の周りに j1 より古い建物がない

                let exists_old = jinjas.iter().copied().any(|j2| {
                    // j2 が j1 の近くにある j1 より古い建物
                    dist_sq(j1.pos, j2.pos) <= k * k && j2.h > j1.h
                });
                !exists_old
            })
            .count() as i64;
        Answer { ans }
    }

    #[allow(dead_code)]
    fn solve_naive(&self) -> Answer {
        todo!();
        // let ans = 0;
        // Answer { ans }
    }
}

#[derive(Clone, Debug, PartialEq, Eq)]
struct Answer {
    ans: i64,
}

impl Answer {
    fn print(&self) {
        println!("{}", self.ans);
    }
}

fn main() {
    Problem::read().solve().print();
}

#[cfg(test)]
mod tests {
    #[allow(unused_imports)]
    use super::*;
    #[allow(unused_imports)]
    use rand::{rngs::SmallRng, seq::SliceRandom, *};

    #[test]
    fn test_problem() {
        assert_eq!(1 + 1, 2);
    }

    #[allow(dead_code)]
    #[derive(Debug)]
    struct WrongTestCase {
        problem: Problem,
        main_ans: Answer,
        naive_ans: Answer,
    }

    #[allow(dead_code)]
    fn check(p: &Problem) -> Option<WrongTestCase> {
        let main_ans = p.solve();
        let naive_ans = p.solve_naive();
        if main_ans != naive_ans {
            Some(WrongTestCase {
                problem: p.clone(),
                main_ans,
                naive_ans,
            })
        } else {
            None
        }
    }

    #[allow(dead_code)]
    fn make_random_problem(rng: &mut SmallRng) -> Problem {
        todo!()
        // let n = rng.gen_range(1..=10);
        // let p = Problem { _a: n };
        // println!("{:?}", &p);
        // p
    }

    #[allow(unreachable_code)]
    #[test]
    fn test_with_naive() {
        let num_tests = 0;
        let max_wrong_case = 10; // この件数間違いが見つかったら打ち切り
        let mut rng = SmallRng::seed_from_u64(42);
        // let mut rng = SmallRng::from_entropy();
        let mut wrong_cases: Vec<WrongTestCase> = vec![];
        for _ in 0..num_tests {
            let p = make_random_problem(&mut rng);
            let result = check(&p);
            if let Some(wrong_test_case) = result {
                wrong_cases.push(wrong_test_case);
            }
            if wrong_cases.len() >= max_wrong_case {
                break;
            }
        }

        if !wrong_cases.is_empty() {
            for t in &wrong_cases {
                println!("{:?}", t.problem);
                println!("main ans : {:?}", t.main_ans);
                println!("naive ans: {:?}", t.naive_ans);
                println!();
            }
            println!("{} cases are wrong.", wrong_cases.len());
            panic!();
        }
    }
}

// ====== import ======
#[allow(unused_imports)]
use proconio::{
    derive_readable, fastout, input,
    marker::{Bytes, Chars, Usize1},
};
#[allow(unused_imports)]
use std::cmp::Reverse;
#[allow(unused_imports)]
use std::collections::{BinaryHeap, HashMap, HashSet};

// ====== output func ======
#[allow(unused_imports)]
use print_vec::*;
pub mod print_vec {

    use proconio::fastout;
    #[fastout]
    pub fn print_vec<T: std::fmt::Debug>(arr: &[T]) {
        for a in arr {
            println!("{:?}", a);
        }
    }
    #[fastout]
    pub fn print_vec_1line<T: std::fmt::Debug>(arr: &[T]) {
        let msg = arr
            .iter()
            .map(|x| format!("{:?}", x))
            .collect::<Vec<String>>()
            .join(" ");
        println!("{}", msg);
    }
    #[fastout]
    pub fn print_vec2<T: std::fmt::Debug>(arr: &Vec<Vec<T>>) {
        for row in arr {
            let msg = row
                .iter()
                .map(|x| format!("{:?}", x))
                .collect::<Vec<String>>()
                .join(" ");
            println!("{}", msg);
        }
    }
    pub fn print_bytes(bytes: &[u8]) {
        let msg = String::from_utf8(bytes.to_vec()).unwrap();
        println!("{}", msg);
    }
    pub fn print_chars(chars: &[char]) {
        let msg = chars.iter().collect::<String>();
        println!("{}", msg);
    }
    #[fastout]
    pub fn print_vec_bytes(vec_bytes: &[Vec<u8>]) {
        for row in vec_bytes {
            let msg = String::from_utf8(row.to_vec()).unwrap();
            println!("{}", msg);
        }
    }
}

#[allow(unused)]
fn print_yesno(ans: bool) {
    let msg = if ans { "Yes" } else { "No" };
    println!("{}", msg);
}

// ====== snippet ======
use pos::*;
pub mod pos {
    use std::ops::{Add, AddAssign, Mul, Neg, Sub, SubAssign};
    #[derive(Clone, Copy, Debug, PartialEq, Eq, PartialOrd, Ord, Hash)]
    pub struct Pos<T> {
        pub x: T,
        pub y: T,
    }
    impl<T> Pos<T> {
        pub fn new(x: T, y: T) -> Pos<T> {
            Pos { x, y }
        }
    }
    impl<T: Mul<Output = T> + Copy> Pos<T> {
        pub fn scala_mul(self, rhs: T) -> Pos<T> {
            Pos::new(self.x * rhs, self.y * rhs)
        }
    }
    impl<T: Add<Output = T> + Mul<Output = T> + Copy> Pos<T> {
        pub fn inner_product(self, rhs: Self) -> T {
            self.x * rhs.x + self.y * rhs.y
        }
        pub fn norm_square(self) -> T {
            self.inner_product(self)
        }
    }
    impl<T: Add<Output = T> + Copy> Add for Pos<T> {
        type Output = Pos<T>;
        fn add(self, rhs: Self) -> Self::Output {
            Pos::new(self.x + rhs.x, self.y + rhs.y)
        }
    }
    impl<T: Sub<Output = T> + Copy> Sub for Pos<T> {
        type Output = Pos<T>;
        fn sub(self, rhs: Self) -> Self::Output {
            Pos::new(self.x - rhs.x, self.y - rhs.y)
        }
    }
    impl<T: Neg<Output = T>> Neg for Pos<T> {
        type Output = Self;
        fn neg(self) -> Self::Output {
            Pos::new(-self.x, -self.y)
        }
    }

    impl<T: Add<Output = T> + Copy> AddAssign for Pos<T> {
        fn add_assign(&mut self, rhs: Self) {
            *self = *self + rhs
        }
    }
    impl<T: Sub<Output = T> + Copy> SubAssign for Pos<T> {
        fn sub_assign(&mut self, rhs: Self) {
            *self = *self - rhs
        }
    }

}