#957488 (Rust) No.2673 A present from B

提出ソース
結果

問題	No.2673 A present from B
ユーザー	ngtkana
提出日時	2024-03-04 03:40:01
言語	Rust (1.77.0)
結果	RE
実行時間	-
コード長	24,163 bytes
コンパイル時間	2,792 ms
コンパイル使用メモリ	215,056 KB
実行使用メモリ	6,676 KB
最終ジャッジ日時	2024-03-13 21:52:11
合計ジャッジ時間	3,171 ms
ジャッジサーバーID （参考情報）	judge13 / judge11
このコードへのチャレンジ
（要ログイン）
テストケース

テストケース表示
入力	結果	実行時間実行使用メモリ
testcase_00	AC	1 ms 6,676 KB
testcase_01	AC	1 ms 6,676 KB
testcase_02	AC	1 ms 6,676 KB
testcase_03	AC	1 ms 6,676 KB
testcase_04	RE	-
testcase_05	AC	1 ms 6,676 KB
testcase_06	RE	-
testcase_07	RE	-
testcase_08	RE	-
testcase_09	AC	1 ms 6,676 KB
testcase_10	AC	1 ms 6,676 KB
testcase_11	AC	1 ms 6,676 KB
testcase_12	RE	-
testcase_13	RE	-
testcase_14	RE	-
testcase_15	RE	-
testcase_16	RE	-
testcase_17	RE	-
testcase_18	RE	-
testcase_19	RE	-
testcase_20	RE	-
testcase_21	RE	-
testcase_22	AC	1 ms 6,676 KB
testcase_23	AC	1 ms 6,676 KB
testcase_24	AC	1 ms 6,676 KB
testcase_25	AC	1 ms 6,676 KB
testcase_26	AC	1 ms 6,676 KB
権限があれば一括ダウンロードができます
ソースコード

raw source code
use input::input_array;
use input::input_vec;
use std::cmp::Ordering;
use std::iter::successors;
use veb::VebSet;

fn main() {
    let [n, _m] = input_array::<usize, 2>();
    let mut a = input_vec::<usize>();
    for x in &mut a {
        *x -= 1;
    }
    let mut dist = Dist {
        table: (0..n).collect(),
        set: VebSet::from_iter(vec![0, n - 1]),
    };
    for &x1 in a.iter().rev() {
        let x2 = x1 + 1;
        if x1 != 0 {
            dist.at(x1 - 1);
        }
        let y1 = *dist.at(x1);
        let y2 = *dist.at(x2);
        if x2 != n - 1 {
            dist.at(x2 + 1);
        }
        match y1.cmp(&y2) {
            Ordering::Equal => {}
            Ordering::Less => {
                if x1 == 0 || *dist.at(x1 - 1) >= *dist.at(x1) {
                    *dist.at(x1) += 1;
                }
                let points = successors(Some(x2), |x| dist.set.succ(*x))
                    .take_while(|&x| dist.table[x] == y2 + x - x2)
                    .collect::<Vec<_>>();
                if points.len() >= 2 {
                    for &x in &points[1..points.len() - 1] {
                        dist.set.remove(x);
                    }
                    let x3 = points[points.len() - 1];
                    if x3 + 1 < n {
                        dist.at(x3 + 1);
                    }
                    *dist.at(x3) -= 1;
                }
                *dist.at(x2) -= 1;
            }
            Ordering::Greater => {
                if x2 == n - 1 || *dist.at(x2 + 1) >= *dist.at(x2) {
                    *dist.at(x2) += 1;
                }
                let points = successors(Some(x1), |x| dist.set.pred(*x))
                    .take_while(|&x| dist.table[x] == y1 + x1 - x)
                    .collect::<Vec<_>>();
                if points.len() >= 2 {
                    for &x in &points[1..points.len() - 1] {
                        dist.set.remove(x);
                    }
                    let x0 = points[points.len() - 1];
                    if x0 > 0 {
                        dist.at(x0 - 1);
                    }
                    *dist.at(x0) -= 1;
                }
                *dist.at(x1) -= 1;
            }
        }
    }
    println!(
        "{}",
        (1..n)
            .map(|i| *dist.at(i))
            .map(|x| x.to_string())
            .collect::<Vec<_>>()
            .join(" ")
    );
}

#[derive(Debug)]
struct Dist {
    table: Vec<usize>,
    set: VebSet,
}
impl Dist {
    fn at(&mut self, x: usize) -> &mut usize {
        let x0 = if self.set.contains(x) { x } else { self.set.pred(x).unwrap() };
        let x1 = if self.set.contains(x) { x } else { self.set.succ(x).unwrap() };
        let y0 = self.table[x0];
        let y1 = self.table[x1];
        assert!(y0 == y1 || y0.abs_diff(y1) == x1 - x0);
        let y = y0 + x - x0;
        self.table[x] = y;
        self.set.insert(x);
        &mut self.table[x]
    }
}

// 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())
    }
}
// }}}
// lg {{{
#[allow(dead_code)]
mod lg {
    use std::borrow::Borrow;
    use std::fmt;
    use std::iter::once;
    #[macro_export]
    macro_rules! lg {
        (@contents $head:expr $(, $tail:expr)*) => {{
            $crate::__lg_internal!($head);
            $(
                eprint!(",");
                $crate::__lg_internal!($tail);
            )*
            eprintln!();
        }};
        ($($expr:expr),* $(,)?) => {{
            eprint!("{}笶ｯ", line!());
            $crate::lg!(@contents $($expr),*)
        }};
    }
    #[doc(hidden)]
    #[macro_export]
    macro_rules! __lg_internal {
        ($value:expr) => {{
            match $value {
                head => {
                    eprint!(
                        " {} = {}",
                        stringify!($value),
                        $crate::lg::__quiet(format!("{:?}", &head))
                    );
                }
            }
        }};
    }
    #[macro_export]
    macro_rules! rows {
        {
            $index_label:literal,
            $(@offset $offset:expr,)?
            $(@verticalbar $verticalbar:expr,)*
            $($(@$label:literal =>)? $values:expr),* $(,)?
        } => {{
            #![allow(unused_assignments)]
            let mut rows = $crate::lg::Rows::default();
            rows.line_number(line!());
            $(rows.offset($offset);)?
            $(rows.verticalbar($verticalbar);)*
            rows.index_label($index_label);
            $({
                let mut label = stringify!($values).to_string();
                if label.starts_with("&") {
                    label = label[1..].to_string();
                }
                $({
                    let label_: &'static str = $label;
                    label = label_.to_string();
                })?
                rows.row(label, $values);
            })*
            eprintln!("{}", rows.to_string_table());
        }};
    }
    #[macro_export]
    macro_rules! table {
        {
            $(@$name:literal => )? $values:expr $(,)?
        } => {{
            #![allow(unused_assignments)]
            let mut name = stringify!($values).to_string();
            if name.starts_with("&") {
                name = name[1..].to_string();
            }
            $({
                let name_: &'static str = $name;
                name = name_.to_string();
            })?
            let mut rows = $crate::lg::Rows::default();
            rows.line_number(line!());
            rows.table_name(name);
            #[allow(array_into_iter)]
            for (i, row) in $values.into_iter().enumerate() {
                rows.row(i.to_string(), row);
            }
            eprintln!("{}", rows.to_string_table());
        }};
    }
    #[doc(hidden)]
    pub fn __quiet(s: impl AsRef<str>) -> String {
        s.as_ref()
            .replace("340282366920938463463374607431768211455", "*") // u128
            .replace("170141183460469231731687303715884105727", "*") // i128
            .replace("18446744073709551615", "*") // u64
            .replace("9223372036854775807", "*") // i64
            .replace("-9223372036854775808", "*") // i64
            .replace("4294967295", "*") // u32
            .replace("2147483647", "*") // i32
            .replace("-2147483648", "*") // i32
            .replace("None", "*")
            .replace("Some", "")
            .replace("true", "#")
            .replace("false", ".")
            .replace(['"', '\''], "")
    }
    #[doc(hidden)]
    #[derive(Default)]
    pub struct Rows {
        line_number: String,
        index_label: String,
        offset: usize,
        verticalbars: Vec<usize>,
        table_name: String,
        rows: Vec<Row>,
    }
    impl Rows {
        pub fn line_number(&mut self, line_number: u32) -> &mut Self {
            self.line_number = format!("{}", line_number);
            self
        }

        pub fn index_label(&mut self, index_label: impl Into<String>) -> &mut Self {
            self.index_label = index_label.into();
            self
        }

        pub fn offset(&mut self, offset: usize) -> &mut Self {
            self.offset = offset;
            self
        }

        pub fn verticalbar(&mut self, verticalbar: impl IntoIterator<Item = usize>) -> &mut Self {
            self.verticalbars.extend(verticalbar);
            self
        }

        pub fn table_name(&mut self, table_name: impl Into<String>) -> &mut Self {
            self.table_name = table_name.into();
            self
        }

        pub fn row(
            &mut self,
            label: impl Into<String>,
            values: impl IntoIterator<Item = impl fmt::Debug>,
        ) -> &mut Self {
            self.rows.push(Row {
                label: label.into(),
                values: values
                    .into_iter()
                    .map(|value| __quiet(format!("{:?}", value)))
                    .collect(),
            });
            self
        }

        pub fn to_string_table(self) -> StringTable {
            let Self {
                line_number,
                index_label,
                offset,
                verticalbars,
                table_name,
                rows,
            } = self;
            let w = rows
                .iter()
                .map(|row| row.values.len())
                .max()
                .unwrap_or_default();
            let mut verticalbar_count = vec![0; w + 1];
            for &v in &verticalbars {
                if (offset..=offset + w).contains(&v) {
                    verticalbar_count[v - offset] += 1;
                }
            }
            StringTable {
                head: StringRow {
                    label: format!(
                        "{line_number}笶ｯ {table_name}{index_label}",
                        index_label = if index_label.is_empty() {
                            String::new()
                        } else {
                            format!("[{}]", index_label)
                        }
                    ),
                    values: (offset..offset + w)
                        .map(|index| index.to_string())
                        .collect(),
                },
                body: rows
                    .iter()
                    .map(|row| StringRow {
                        label: row.label.clone(),
                        values: row.values.clone(),
                    })
                    .collect(),
                verticalbar_count,
            }
        }
    }
    struct Row {
        label: String,
        values: Vec<String>,
    }
    #[doc(hidden)]
    pub struct StringTable {
        head: StringRow,
        body: Vec<StringRow>,
        verticalbar_count: Vec<usize>,
    }
    impl fmt::Display for StringTable {
        fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
            let Self {
                head,
                body,
                verticalbar_count,
            } = self;
            let w = body
                .iter()
                .map(|row| row.values.len())
                .max()
                .unwrap_or_default();
            let label_width = once(head.label.chars().count())
                .chain(body.iter().map(|row| row.label.chars().count()))
                .max()
                .unwrap();
            let value_width = (0..w)
                .map(|j| {
                    once(j.to_string().len())
                        .chain(
                            body.iter()
                                .map(|row| row.values.get(j).map_or(0, |s| s.chars().count())),
                        )
                        .max()
                        .unwrap()
                })
                .collect::<Vec<_>>();
            // Heading
            gray(f)?;
            write!(
                f,
                "{}",
                head.to_string(label_width, &value_width, verticalbar_count, true)
            )?;
            resetln(f)?;
            // Body
            for row in body {
                write!(
                    f,
                    "{}",
                    row.to_string(label_width, &value_width, verticalbar_count, false)
                )?;
                writeln!(f)?;
            }
            Ok(())
        }
    }
    struct StringRow {
        label: String,
        values: Vec<String>,
    }
    impl StringRow {
        fn to_string(
            &self,
            label_width: usize,
            value_width: &[usize],
            varticalbars_count: &[usize],
            label_align_left: bool,
        ) -> String {
            let Self { label, values } = self;
            let w = value_width.len();
            let mut s = String::new();
            s.push_str(&if label_align_left {
                format!("{label:<label_width$} |")
            } else {
                format!("{label:^label_width$} |")
            });
            for j in 0..w {
                let value_width = value_width[j];
                s.push_str("|".repeat(varticalbars_count[j]).as_str());
                if varticalbars_count[j] == 0 && j != 0 && value_width <= 1 {
                    s.push(' ');
                }
                match values.get(j) {
                    Some(value) => {
                        s.push_str(&format!(" {value:>value_width$}",));
                    }
                    None => {
                        s.push_str(" ".repeat(value_width + 1).as_str());
                    }
                }
            }
            s
        }
    }
    const GRAY: &str = "\x1b[48;2;127;127;127;37m";
    const RESET: &str = "\x1b[0m";
    fn gray(f: &mut fmt::Formatter<'_>) -> fmt::Result {
        write!(f, "{GRAY}")
    }
    fn resetln(f: &mut fmt::Formatter<'_>) -> fmt::Result {
        writeln!(f, "{RESET}")
    }
    pub fn bools<B, I>(iter: I) -> String
    where
        B: Borrow<bool>,
        I: IntoIterator<Item = B>,
    {
        format!(
            "[{}]",
            iter.into_iter()
                .map(|b| ['.', '#'][usize::from(*(b.borrow()))])
                .collect::<String>(),
        )
    }
}
// }}}
// veb {{{
#[allow(dead_code)]
mod veb {
    use std::collections::HashMap;
    macro_rules! multi_or_else {
        ($e:expr, $($f:expr),+) => {
            $e.or_else(|| multi_or_else!($($f),+))
        };
        ($e:expr) => {
            $e
        };
    }
    pub enum VebSet {
        Internal {
            min: usize,
            max: usize,
            len: usize,
            csize: usize,
            summary: Box<VebSet>,
            chunks: HashMap<usize, VebSet>,
        },
        Leaf(u64),
    }
    impl VebSet {
        pub fn new(n: usize) -> Self {
            if n <= 64 {
                VebSet::Leaf(0)
            } else {
                let csize = (n as f64).sqrt().ceil() as usize;
                let ccount = (n + csize - 1) / csize;
                Self::Internal {
                    min: 0,
                    max: 0,
                    csize,
                    len: 0,
                    summary: Box::new(VebSet::new(ccount)),
                    chunks: HashMap::new(),
                }
            }
        }

        pub fn min(&self) -> Option<usize> {
            match self {
                Self::Internal { min, len, .. } => Some(*min).filter(|_| *len > 0),
                Self::Leaf(bs) => Some(bs.trailing_zeros() as usize).filter(|&i| i < 64),
            }
        }

        pub fn max(&self) -> Option<usize> {
            match self {
                Self::Internal { max, len, .. } => Some(*max).filter(|_| *len > 0),
                Self::Leaf(bs) => bs.checked_ilog2().map(|i| i as usize),
            }
        }

        pub fn len(&self) -> usize {
            match self {
                Self::Internal { len, .. } => *len,
                Self::Leaf(bs) => bs.count_ones() as usize,
            }
        }

        pub fn is_empty(&self) -> bool {
            self.len() == 0
        }

        pub fn insert(&mut self, mut i: usize) -> bool {
            match self {
                Self::Internal {
                    min,
                    max,
                    csize,
                    len,
                    summary,
                    chunks,
                } => {
                    if *len == 0 {
                        *min = i;
                        *max = i;
                        *len = 1;
                        true
                    } else {
                        if i < *min {
                            std::mem::swap(&mut i, min);
                        }
                        *max = (*max).max(i);
                        if i == *min {
                            return false;
                        }
                        let j = i / *csize;
                        let k = i % *csize;
                        let result = if let Some(chunk) = chunks.get_mut(&j) {
                            chunk.insert(k)
                        } else {
                            let mut chunk = VebSet::new(*csize);
                            assert!(chunk.insert(k));
                            chunks.insert(j, chunk);
                            summary.insert(j);
                            true
                        };
                        if result {
                            *len += 1;
                        }
                        result
                    }
                }
                Self::Leaf(bs) => {
                    let result = *bs >> i & 1;
                    *bs |= 1 << i;
                    result == 0
                }
            }
        }

        pub fn remove(&mut self, mut i: usize) -> bool {
            match self {
                Self::Internal {
                    min,
                    max,
                    csize,
                    len,
                    summary,
                    chunks,
                } => match len {
                    0 => false,
                    1 => {
                        let result = i == *min;
                        if result {
                            *min = 0;
                            *max = 0;
                            *len = 0;
                        }
                        result
                    }
                    _ => {
                        if i == *min {
                            let j = summary.min().unwrap();
                            i = j * *csize + chunks[&j].min().unwrap();
                            *min = i;
                        }
                        let j = i / *csize;
                        let k = i % *csize;
                        let result = chunks.get_mut(&j).map_or(false, |chunk| chunk.remove(k));
                        if result {
                            *len -= 1;
                            if chunks[&j].is_empty() {
                                chunks.remove(&j);
                                summary.remove(j);
                            }
                            if i == *max {
                                *max = if let Some(j) = summary.max() {
                                    j * *csize + chunks[&j].max().unwrap()
                                } else {
                                    *min
                                };
                            }
                        }
                        result
                    }
                },
                Self::Leaf(bs) => {
                    let result = *bs >> i & 1;
                    *bs &= !(1 << i);
                    result == 1
                }
            }
        }

        pub fn succ(&self, i: usize) -> Option<usize> {
            match self {
                Self::Internal {
                    min,
                    max,
                    len,
                    csize,
                    summary,
                    chunks,
                    ..
                } => {
                    let j = i / csize;
                    let k = i % csize;
                    match () {
                        () if *len == 0 || *max <= i => None,
                        () if i < *min => Some(*min),
                        () => multi_or_else!(
                            chunks
                                .get(&j)
                                .and_then(|chunk| chunk.succ(k))
                                .map(|k1| j * csize + k1),
                            summary
                                .succ(j)
                                .map(|j1| j1 * csize + chunks[&j1].min().unwrap())
                        ),
                    }
                }
                &Self::Leaf(bs) => match i {
                    63 => None,
                    _ => Some(i + 1 + (bs >> (i + 1)).trailing_zeros() as usize)
                        .filter(|&i1| i1 < 64),
                },
            }
        }

        pub fn pred(&self, i: usize) -> Option<usize> {
            match self {
                Self::Internal {
                    min,
                    max,
                    csize,
                    len,
                    summary,
                    chunks,
                } => {
                    let j = i / csize;
                    let k = i % csize;
                    match () {
                        () if *len == 0 || i <= *min => None,
                        () if *max < i => Some(*max),
                        () => multi_or_else!(
                            chunks
                                .get(&j)
                                .and_then(|chunk| chunk.pred(k))
                                .map(|k1| { j * csize + k1 }),
                            summary
                                .pred(j)
                                .map(|j1| { j1 * csize + chunks[&j1].max().unwrap() }),
                            Some(*min)
                        ),
                    }
                }
                &Self::Leaf(bs) => (bs & ((1 << i) - 1)).checked_ilog2().map(|j| j as usize),
            }
        }

        pub fn contains(&self, i: usize) -> bool {
            match self {
                #[allow(unused_variables)]
                Self::Internal {
                    min,
                    max,
                    csize,
                    len,
                    summary,
                    chunks,
                } => {
                    let j = i / csize;
                    let k = i % csize;
                    *len != 0
                        && (i == *min || chunks.get(&j).map_or(false, |chunk| chunk.contains(k)))
                }
                Self::Leaf(bs) => bs >> i & 1 == 1,
            }
        }

        pub fn collect(&self) -> Vec<usize> {
            let mut result = Vec::with_capacity(self.len());
            let mut i = self.min();
            for _ in 0..self.len() {
                result.push(i.unwrap());
                i = self.succ(i.unwrap());
            }
            result
        }
    }
    impl Default for VebSet {
        fn default() -> Self {
            Self::new(0)
        }
    }
    impl std::iter::FromIterator<usize> for VebSet {
        fn from_iter<T: IntoIterator<Item = usize>>(iter: T) -> Self {
            let mut veb = VebSet::default();
            for i in iter {
                veb.insert(i);
            }
            veb
        }
    }
    impl std::fmt::Debug for VebSet {
        fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
            f.debug_set().entries(self.collect()).finish()
        }
    }
}
// }}}
yukicoder

結果

テストケース

ソースコード
