結果
問題 | No.2673 A present from B |
ユーザー |
![]() |
提出日時 | 2024-03-04 03:41:27 |
言語 | Rust (1.83.0 + proconio) |
結果 |
AC
|
実行時間 | 2 ms / 2,000 ms |
コード長 | 23,922 bytes |
コンパイル時間 | 14,771 ms |
コンパイル使用メモリ | 389,920 KB |
実行使用メモリ | 6,820 KB |
最終ジャッジ日時 | 2024-09-29 23:28:02 |
合計ジャッジ時間 | 14,745 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 24 |
ソースコード
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::new(n),};dist.set.insert(0);dist.set.insert(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 TwhereT: 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]whereT: 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<_>>();// Headinggray(f)?;write!(f,"{}",head.to_string(label_width, &value_width, verticalbar_count, true))?;resetln(f)?;// Bodyfor 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) -> StringwhereB: 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::fmt::Debug for VebSet {fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {f.debug_set().entries(self.collect()).finish()}}}// }}}