結果
| 問題 | No.2673 A present from B |
| ユーザー |
 ngtkana
|
| 提出日時 | 2024-03-05 18:26:14 |
| 言語 | Rust (1.77.0 + proconio) |
| 結果 |
WA
|
| 実行時間 | - |
| コード長 | 16,319 bytes |
| コンパイル時間 | 12,688 ms |
| コンパイル使用メモリ | 402,936 KB |
| 実行使用メモリ | 6,824 KB |
| 最終ジャッジ日時 | 2024-09-29 23:29:36 |
| 合計ジャッジ時間 | 13,717 ms |
|
ジャッジサーバーID （参考情報） |
judge1 / judge2 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | WA | - |
| testcase_01 | WA | - |
| testcase_02 | WA | - |
| testcase_03 | WA | - |
| testcase_04 | WA | - |
| testcase_05 | WA | - |
| testcase_06 | WA | - |
| testcase_07 | WA | - |
| testcase_08 | WA | - |
| testcase_09 | WA | - |
| testcase_10 | WA | - |
| testcase_11 | WA | - |
| testcase_12 | WA | - |
| testcase_13 | WA | - |
| testcase_14 | WA | - |
| testcase_15 | WA | - |
| testcase_16 | WA | - |
| testcase_17 | WA | - |
| testcase_18 | WA | - |
| testcase_19 | WA | - |
| testcase_20 | WA | - |
| testcase_21 | WA | - |
| testcase_22 | WA | - |
| testcase_23 | WA | - |
| testcase_24 | WA | - |
| testcase_25 | WA | - |
| testcase_26 | WA | - |
ソースコード
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 / 2);
dist.insert(1, 0);
dist.insert(n, n - 1);
dist.insert(n + 1, usize::MAX / 2);
macro_rules! lerp {
($x:expr) => {
lerp(&mut dist, $x)
};
}
for &x1 in a.iter().rev() {
let x2 = x1 + 1;
lerp!(x1 - 1);
let y1 = lerp!(x1);
let y2 = lerp!(x2);
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;
}
if let Some((mut x3, mut y3)) = dist
.succ(x2)
.map(|(x, &y)| (x, y))
.filter(|&(x, y)| y == y2 + x - x2)
{
while let Some((x, y)) = dist
.succ(x3)
.map(|(x, &y)| (x, y))
.filter(|&(x, y)| y == y3 + x - x3)
{
dist.remove(x3);
x3 = x;
y3 = y;
}
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;
}
if let Some((mut x0, mut y0)) = dist
.pred(x1)
.map(|(x, &y)| (x, y))
.filter(|&(x, y)| y == y1 + x1 - x)
{
while let Some((x, y)) = dist
.pred(x0)
.map(|(x, &y)| (x, y))
.filter(|&(x, y)| y == y0 + x0 - x)
{
dist.remove(x0);
x0 = x;
y0 = y;
}
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())
}
}
// }}}
// 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()
}
}
}
// }}}