結果

問題 No.2673 A present from B
コンテスト
ユーザー ngtkana
提出日時 2024-03-06 01:10:44
言語 Rust
(1.83.0 + proconio)
結果
AC  
実行時間 2 ms / 2,000 ms
コード長 4,371 bytes
コンパイル時間 15,224 ms
コンパイル使用メモリ 378,300 KB
実行使用メモリ 5,248 KB
最終ジャッジ日時 2024-09-29 23:34:13
合計ジャッジ時間 16,055 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 24
権限があれば一括ダウンロードができます

ソースコード

diff # 

use input::input_array;
use input::input_vec;
use std::cmp::Ordering;
use std::collections::BTreeMap;

fn main() {
    let [n, _m] = input_array::<usize, 2>();
    let a = input_vec::<usize>();
    let mut dist = BTreeMap::from_iter(vec![
        (0, usize::MAX),
        (1, 0),
        (n, n - 1),
        (n + 1, usize::MAX),
    ]);
    for &x1 in a.iter().rev() {
        let x2 = x1 + 1;
        lerp(&mut dist, x1);
        lerp(&mut dist, x2);
        match dist[&x1].cmp(&dist[&x2]) {
            Ordering::Equal => {}
            Ordering::Less => {
                let section = dist[&x1] as isize - x1 as isize;
                let on_line = |&(x, y): &(&usize, &usize)| *y as isize == section + *x as isize;
                lerp(&mut dist, x1 - 1);
                *dist.get_mut(&x1).unwrap() += usize::from(dist[&(x1 - 1)] >= dist[&x1]);
                if let Some((&(mut x3), &(mut y3))) = dist.range(x2 + 1..).next().filter(on_line) {
                    while let Some((&x, &y)) = dist.range(x3 + 1..).next().filter(on_line) {
                        dist.remove(&x3);
                        (x3, y3) = (x, y);
                    }
                    lerp(&mut dist, x3 + 1);
                    dist.insert(x3, y3 - 1);
                }
                dist.insert(x2, dist[&x2] - 1);
            }
            Ordering::Greater => {
                let section = dist[&x2] as isize + x2 as isize;
                let on_line = |&(x, y): &(&usize, &usize)| *y as isize == section - *x as isize;
                lerp(&mut dist, x2 + 1);
                *dist.get_mut(&x2).unwrap() += usize::from(dist[&(x2 + 1)] >= dist[&x2]);
                if let Some((&(mut x0), &(mut y0))) = dist.range(..x1).next_back().filter(on_line) {
                    while let Some((&x, &y)) = dist.range(..x0).next_back().filter(on_line) {
                        dist.remove(&x0);
                        (x0, y0) = (x, y);
                    }
                    lerp(&mut dist, x0 - 1);
                    dist.insert(x0, y0 - 1);
                }
                dist.insert(x1, dist[&x1] - 1);
            }
        }
    }
    println!(
        "{}",
        (2..=n)
            .map(|i| {
                lerp(&mut dist, i);
                dist[&i].to_string()
            })
            .collect::<Vec<_>>()
            .join(" ")
    );
}

fn lerp(map: &mut BTreeMap<usize, usize>, x: usize) {
    if !map.contains_key(&x) {
        let (x0, &y0) = map.range(..=x).next_back().unwrap();
        let (x1, &y1) = map.range(x..).next().unwrap();
        assert!(y0 == y1 || y0.abs_diff(y1) == x1 - x0);
        let y = y0 + (x - x0) * (y1 - y0) / (x1 - x0);
        map.insert(x, y);
    }
}

// input {{{
#[allow(dead_code)]
mod input {
    use std::cell::Cell;
    use std::convert::TryFrom;
    use std::io::stdin;
    use std::io::BufRead;
    use std::io::BufReader;
    use std::io::Lines;
    use std::io::Stdin;
    use std::str::FromStr;
    use std::sync::Mutex;
    use std::sync::Once;
    type Server = Mutex<Lines<BufReader<Stdin>>>;
    static ONCE: Once = Once::new();
    pub struct Lazy(Cell<Option<Server>>);
    unsafe impl Sync for Lazy {}
    fn line() -> String {
        static SYNCER: Lazy = Lazy(Cell::new(None));
        ONCE.call_once(|| {
            SYNCER
                .0
                .set(Some(Mutex::new(BufReader::new(stdin()).lines())));
        });
        unsafe {
            (*SYNCER.0.as_ptr())
                .as_ref()
                .unwrap()
                .lock()
                .unwrap()
                .next()
                .unwrap()
                .unwrap()
        }
    }
    pub trait ForceFromStr: FromStr {
        fn force_from_str(s: &str) -> Self;
    }
    impl<T, E> ForceFromStr for T
    where
        T: FromStr<Err = E>,
        E: std::fmt::Debug,
    {
        fn force_from_str(s: &str) -> Self {
            s.parse().unwrap()
        }
    }
    pub fn input_array<T: ForceFromStr, const N: usize>() -> [T; N]
    where
        T: std::fmt::Debug,
    {
        <[_; N]>::try_from(input_vec()).unwrap()
    }
    pub fn input_vec<T: ForceFromStr>() -> Vec<T> {
        line()
            .split_whitespace()
            .map(T::force_from_str)
            .collect::<Vec<_>>()
    }
    pub fn input<T: ForceFromStr>() -> T {
        T::force_from_str(&line())
    }
}
// }}}
0