結果
問題 | No.2673 A present from B |
ユーザー |
![]() |
提出日時 | 2024-03-06 00:49:40 |
言語 | Rust (1.83.0 + proconio) |
結果 |
RE
|
実行時間 | - |
コード長 | 16,657 bytes |
コンパイル時間 | 15,190 ms |
コンパイル使用メモリ | 387,356 KB |
実行使用メモリ | 6,820 KB |
最終ジャッジ日時 | 2024-09-29 23:33:25 |
合計ジャッジ時間 | 14,130 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 13 RE * 11 |
コンパイルメッセージ
warning: unreachable expression --> src/main.rs:42:21 | 41 | panic!(); | -------- any code following this expression is unreachable 42 | y == x.checked_add_signed(section).unwrap() | ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ unreachable expression | = note: `#[warn(unreachable_code)]` on by default warning: unused variable: `x` --> src/main.rs:40:32 | 40 | let on_line = |x: usize, y: usize| { | ^ help: if this is intentional, prefix it with an underscore: `_x` | = note: `#[warn(unused_variables)]` on by default warning: unused variable: `y` --> src/main.rs:40:42 | 40 | let on_line = |x: usize, y: usize| { | ^ help: if this is intentional, prefix it with an underscore: `_y`
ソースコード
use input::input_array;use input::input_vec;use std::cmp::Ordering;use veb::VebMap;fn main() {let [n, _m] = input_array::<usize, 2>();let a = input_vec::<usize>();let mut dist = VebMap::new(n + 2);dist.insert(0, usize::MAX);dist.insert(1, 0);dist.insert(n, n - 1);dist.insert(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: usize, y: usize| y == x.checked_add_signed(section).unwrap();lerp(&mut dist, x1 - 1);if dist[x1 - 1] >= dist[x1] {*dist.get_mut(x1).unwrap() += 1;}if let Some((mut x3, &(mut y3))) = dist.succ(x2).filter(|&(x, &y)| on_line(x, y)) {while let Some((x, &y)) = dist.succ(x3).filter(|&(x, &y)| on_line(x, y)) {dist.remove(x3);(x3, y3) = (x, y);}lerp(&mut dist, x3 + 1);dist.insert(x3, y3 - 1);}let y2 = dist[x2];dist.insert(x2, y2 - 1);}Ordering::Greater => {let section = x2 as isize - dist[x2] as isize;let on_line = |x: usize, y: usize| {panic!();y == x.checked_add_signed(section).unwrap()};lerp(&mut dist, x2 + 1);if dist[x2 + 1] >= dist[x2] {*dist.get_mut(x2).unwrap() += 1;}if let Some((mut x3, &(mut y3))) = dist.pred(x1).filter(|&(x, &y)| on_line(x, y)) {while let Some((x, &y)) = dist.pred(x3).filter(|&(x, &y)| on_line(x, y)) {dist.remove(x3);(x3, y3) = (x, y);}lerp(&mut dist, x3 - 1);dist.insert(x3, y3 - 1);}let y1 = dist[x1];dist.insert(x1, y1 - 1);}}}println!("{}",(2..=n).map(|i| {lerp(&mut dist, i);dist.get(i).unwrap().to_string()}).collect::<Vec<_>>().join(" "));}fn lerp(map: &mut VebMap<usize>, x: usize) {if !map.contains_key(x) {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);}}// 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())}}// }}}// 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 contains_key(&self, i: usize) -> bool {self.veb.contains(i)}pub fn collect(&self) -> Vec<(usize, &V)> {self.veb.collect().into_iter().filter_map(|i| self.map.get(&i).map(|v| (i, v))).collect()}}impl<V> std::ops::Index<usize> for VebMap<V> {type Output = V;fn index(&self, i: usize) -> &V {self.get(i).unwrap()}}impl<V> std::ops::IndexMut<usize> for VebMap<V> {fn index_mut(&mut self, i: usize) -> &mut V {self.get_mut(i).unwrap()}}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 {Self::Internal {min,csize,len,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()}}}// }}}