結果
問題 | No.2673 A present from B |
ユーザー | ngtkana |
提出日時 | 2024-03-05 16:51:21 |
言語 | Rust (1.77.0 + proconio) |
結果 |
AC
|
実行時間 | 2 ms / 2,000 ms |
コード長 | 26,481 bytes |
コンパイル時間 | 12,487 ms |
コンパイル使用メモリ | 388,560 KB |
実行使用メモリ | 6,820 KB |
最終ジャッジ日時 | 2024-09-29 23:28:35 |
合計ジャッジ時間 | 13,779 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge3 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 1 ms
6,820 KB |
testcase_01 | AC | 1 ms
6,816 KB |
testcase_02 | AC | 1 ms
6,816 KB |
testcase_03 | AC | 1 ms
6,816 KB |
testcase_04 | AC | 1 ms
6,816 KB |
testcase_05 | AC | 1 ms
6,820 KB |
testcase_06 | AC | 2 ms
6,820 KB |
testcase_07 | AC | 2 ms
6,820 KB |
testcase_08 | AC | 1 ms
6,820 KB |
testcase_09 | AC | 1 ms
6,820 KB |
testcase_10 | AC | 1 ms
6,816 KB |
testcase_11 | AC | 1 ms
6,820 KB |
testcase_12 | AC | 1 ms
6,816 KB |
testcase_13 | AC | 1 ms
6,820 KB |
testcase_14 | AC | 1 ms
6,820 KB |
testcase_15 | AC | 1 ms
6,820 KB |
testcase_16 | AC | 2 ms
6,820 KB |
testcase_17 | AC | 1 ms
6,816 KB |
testcase_18 | AC | 1 ms
6,816 KB |
testcase_19 | AC | 1 ms
6,816 KB |
testcase_20 | AC | 1 ms
6,816 KB |
testcase_21 | AC | 2 ms
6,816 KB |
testcase_22 | AC | 1 ms
6,816 KB |
testcase_23 | AC | 1 ms
6,816 KB |
testcase_24 | AC | 1 ms
6,820 KB |
testcase_25 | AC | 1 ms
6,816 KB |
testcase_26 | AC | 1 ms
6,820 KB |
ソースコード
use input::input_array; use input::input_vec; use std::cmp::Ordering; use std::iter::successors; use veb::VebMap; 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 = VebMap::new(n); dist.insert(0, 0); dist.insert(n - 1, n - 1); macro_rules! lerp { ($x:expr) => { lerp(&mut dist, $x) }; } for &x1 in a.iter().rev() { let x2 = x1 + 1; if x1 != 0 { lerp!(x1 - 1); } let y1 = lerp!(x1); let y2 = lerp!(x2); if x2 != n - 1 { lerp!(x2 + 1); } match y1.cmp(&y2) { Ordering::Equal => {} Ordering::Less => { if x1 == 0 || lerp!(x1 - 1) >= lerp!(x1) { *dist.get_mut(x1).unwrap() += 1; } let points = successors(Some((x2, y2)), |&(x, _)| dist.succ(x).map(|(x, &y)| (x, y))) .take_while(|&(x, y)| y == y2 + x - x2) .collect::<Vec<_>>(); if points.len() >= 2 { for &(x, _) in &points[1..points.len() - 1] { dist.remove(x); } let (x3, y3) = points[points.len() - 1]; if x3 + 1 < n { lerp!(x3 + 1); } dist.insert(x3, y3 - 1); } dist.insert(x2, y2 - 1); } Ordering::Greater => { if x2 == n - 1 || lerp!(x2 + 1) >= lerp!(x2) { *dist.get_mut(x2).unwrap() += 1; } let points = successors(Some((x1, y1)), |&(x, _)| dist.pred(x).map(|(x, &y)| (x, y))) .take_while(|&(x, y)| y == y1 + x1 - x) .collect::<Vec<_>>(); if points.len() >= 2 { for &(x, _) in &points[1..points.len() - 1] { dist.remove(x); } let (x0, y0) = points[points.len() - 1]; if x0 > 0 { lerp!(x0 - 1); } dist.insert(x0, y0 - 1); } dist.insert(x1, y1 - 1); } } } println!( "{}", (1..n) .map(|i| lerp!(i)) .map(|x| x.to_string()) .collect::<Vec<_>>() .join(" ") ); } fn lerp(map: &mut VebMap<usize>, x: usize) -> usize { if let Some(&y) = map.get(x) { return y; } let (x0, &y0) = map.pred(x).unwrap(); let (x1, &y1) = map.succ(x).unwrap(); assert!(y0 == y1 || y0.abs_diff(y1) == x1 - x0); let y = y0 + (x - x0) * (y1 - y0) / (x1 - x0); map.insert(x, y); 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()) } } // }}} // 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 struct VebMap<V> { veb: VebSet, map: HashMap<usize, V>, } impl<V> VebMap<V> { pub fn new(n: usize) -> Self { Self { veb: VebSet::new(n), map: HashMap::new(), } } pub fn insert(&mut self, i: usize, v: V) -> Option<V> { self.veb.insert(i); self.map.insert(i, v) } pub fn remove(&mut self, i: usize) -> Option<V> { self.veb.remove(i); self.map.remove(&i) } pub fn get(&self, i: usize) -> Option<&V> { self.map.get(&i) } pub fn get_mut(&mut self, i: usize) -> Option<&mut V> { self.map.get_mut(&i) } pub fn min_key(&self) -> Option<usize> { self.veb.min() } pub fn min_value(&self) -> Option<&V> { self.veb.min().and_then(|i| self.map.get(&i)) } pub fn min(&self) -> Option<(usize, &V)> { self.veb .min() .and_then(|i| self.map.get(&i).map(|v| (i, v))) } pub fn max_key(&self) -> Option<usize> { self.veb.max() } pub fn max_value(&self) -> Option<&V> { self.veb.max().and_then(|i| self.map.get(&i)) } pub fn max(&self) -> Option<(usize, &V)> { self.veb .max() .and_then(|i| self.map.get(&i).map(|v| (i, v))) } pub fn succ_key(&self, i: usize) -> Option<usize> { self.veb.succ(i) } pub fn succ_value(&self, i: usize) -> Option<&V> { self.veb.succ(i).and_then(|i| self.map.get(&i)) } pub fn succ(&self, i: usize) -> Option<(usize, &V)> { self.veb .succ(i) .and_then(|i| self.map.get(&i).map(|v| (i, v))) } pub fn pred_key(&self, i: usize) -> Option<usize> { self.veb.pred(i) } pub fn pred_value(&self, i: usize) -> Option<&V> { self.veb.pred(i).and_then(|i| self.map.get(&i)) } pub fn pred(&self, i: usize) -> Option<(usize, &V)> { self.veb .pred(i) .and_then(|i| self.map.get(&i).map(|v| (i, v))) } pub fn len(&self) -> usize { self.veb.len() } pub fn is_empty(&self) -> bool { self.veb.is_empty() } pub fn collect(&self) -> Vec<(usize, &V)> { self.veb .collect() .into_iter() .filter_map(|i| self.map.get(&i).map(|v| (i, v))) .collect() } } 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 std::fmt::Debug for VebSet { fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result { f.debug_set().entries(self.collect()).finish() } } } // }}}