結果
問題 | No.2673 A present from B |
ユーザー |
![]() |
提出日時 | 2024-03-06 01:19:41 |
言語 | Rust (1.83.0 + proconio) |
結果 |
WA
|
実行時間 | - |
コード長 | 4,304 bytes |
コンパイル時間 | 12,236 ms |
コンパイル使用メモリ | 386,932 KB |
実行使用メモリ | 6,824 KB |
最終ジャッジ日時 | 2024-09-29 23:34:29 |
合計ジャッジ時間 | 13,438 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 WA * 2 |
other | AC * 5 WA * 19 |
ソースコード
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::<isize>();let mut dist = BTreeMap::from_iter(vec![(0, isize::MAX),(1, 0),(n as isize, n as isize - 1),(n as isize + 1, isize::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] - x1;let on_line = |&(x, y): &(&isize, &isize)| *y == section + x;lerp(&mut dist, x1 - 1);*dist.get_mut(&x1).unwrap() += isize::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] + x2;let on_line = |&(x, y): &(&isize, &isize)| *y == section - *x;lerp(&mut dist, x2 + 1);*dist.get_mut(&x2).unwrap() += isize::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 as isize);dist[&(i as isize)].to_string()}).collect::<Vec<_>>().join(" "));}fn lerp(map: &mut BTreeMap<isize, isize>, x: isize) {if !map.contains_key(&x) {let (&x0, &y0) = map.range(..=x).next_back().unwrap();let (&x1, &y1) = map.range(x..).next().unwrap();matches!((y1 - y0) / (x1 - x0), -1..=1);let y = y0;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())}}// }}}