結果

問題 No.2673 A present from B
ユーザー ngtkana
提出日時 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
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

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 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())
}
}
// }}}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0