結果

問題 No.2673 A present from B
ユーザー ngtkana
提出日時 2024-03-04 03:20:16
言語 Rust
(1.83.0 + proconio)
結果
AC  
実行時間 3 ms / 2,000 ms
コード長 17,120 bytes
コンパイル時間 12,956 ms
コンパイル使用メモリ 400,296 KB
実行使用メモリ 5,248 KB
最終ジャッジ日時 2024-09-29 23:26:21
合計ジャッジ時間 14,005 ms
ジャッジサーバーID
(参考情報)
judge1 / judge2
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
sample AC * 3
other AC * 24
権限があれば一括ダウンロードができます
コンパイルメッセージ
warning: associated items `new` and `to_vec` are never used
   --> src/main.rs:145:8
    |
144 | impl Dist {
    | --------- associated items in this implementation
145 |     fn new() -> Self {
    |        ^^^
...
160 |     fn to_vec(&self) -> Vec<usize> {
    |        ^^^^^^
    |
    = note: `#[warn(dead_code)]` on by default

ソースコード

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

use input::input_array;
use input::input_vec;
use std::cmp::Ordering;
use std::collections::BTreeMap;
use std::ops::Bound;
fn main() {
let [n, _m] = input_array::<usize, 2>();
let mut a = input_vec::<usize>();
for x in &mut a {
*x -= 1;
}
let mut old = (0..n as isize).collect::<Vec<_>>();
let mut dist = Dist {
dist: BTreeMap::from_iter(vec![(0, 0), (n - 1, 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 x3 = dist
.range(x2..)
.take_while(|&(&x3, &y3)| y3 == y2 + x3 - x2)
.last()
.map(|(&x3, _)| x3)
.unwrap();
if x2 != x3 {
while let Some(x) = dist
.range((Bound::Excluded(x2), Bound::Excluded(x3)))
.next()
.map(|(x, _)| *x)
{
dist.remove(&x);
}
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) <= *dist.at(x2 + 1) {
*dist.at(x2) += 1;
}
let x0 = dist
.range(..=x1)
.rev()
.take_while(|&(&x0, &y0)| y0 == y1 + x1 - x0)
.last()
.map(|(&x0, _)| x0)
.unwrap();
if x0 != x1 {
while let Some(x) = dist
.range((Bound::Excluded(x0), Bound::Excluded(x1)))
.next()
.map(|(x, _)| *x)
{
dist.remove(&x);
}
if x0 != 0 {
dist.at(x0 - 1);
}
*dist.at(x0) -= 1;
}
*dist.at(x1) -= 1;
}
}
let x = x1;
old.swap(x, x + 1);
if let Some((smaller, larger, to_smaller)) = match old[x].cmp(&old[x + 1]) {
Ordering::Equal => None,
Ordering::Less => Some((x, x + 1, -1)),
Ordering::Greater => Some((x + 1, x, 1)),
} {
let to_larger = -to_smaller;
if let Some(larger_next) = larger.checked_add_signed(to_larger).filter(|&i| i < n) {
if old[larger_next] + 1 < old[larger] {
old[larger] = old[larger_next] + 1;
}
}
{
let mut smaller = smaller;
while let Some(smaller_next) =
smaller
.checked_add_signed(to_smaller)
.filter(|&smaller_next| {
smaller_next < n && old[smaller] + 1 < old[smaller_next]
})
{
old[smaller_next] -= 1;
smaller = smaller_next;
}
}
}
assert!(dist.dist.contains_key(&0));
assert!(dist.dist.contains_key(&(n - 1)));
for ((&x0, &y0), (&x1, &y1)) in dist.dist.range(..).zip(dist.dist.range(..)) {
assert!(y0 == y1 || y0.abs_diff(y1) == x1 - x0);
assert_eq!(y0, old[x0] as usize);
assert_eq!(y1, old[x1] as usize);
}
}
println!(
"{}",
(1..n)
.map(|i| *dist.at(i))
.map(|x| x.to_string())
.collect::<Vec<_>>()
.join(" ")
);
}
#[derive(Debug)]
struct Dist {
dist: BTreeMap<usize, usize>,
}
impl std::ops::Deref for Dist {
type Target = BTreeMap<usize, usize>;
fn deref(&self) -> &Self::Target {
&self.dist
}
}
impl std::ops::DerefMut for Dist {
fn deref_mut(&mut self) -> &mut Self::Target {
&mut self.dist
}
}
impl Dist {
fn new() -> Self {
Self {
dist: BTreeMap::new(),
}
}
fn at(&mut self, x: usize) -> &mut usize {
let (&x0, &y0) = self.dist.range(..=x).next_back().unwrap();
let (&x1, &y1) = self.dist.range(x..).next().unwrap();
assert!(y0 == y1 || y0.abs_diff(y1) == x1 - x0);
let y = y0 + x - x0;
self.dist.insert(x, y);
self.dist.get_mut(&x).unwrap()
}
fn to_vec(&self) -> Vec<usize> {
(0..self.dist.len())
.map(|x| {
let (&x0, &y0) = self.dist.range(..=x).next_back().unwrap();
let (&x1, &y1) = self.dist.range(x..).next().unwrap();
assert!(y0 == y1 || y0.abs_diff(y1) == x1 - x0);
let y = y0 + x - x0;
y
})
.collect::<Vec<_>>()
}
}
// 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())
}
}
// }}}
// 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<_>>();
// Heading
gray(f)?;
write!(
f,
"{}",
head.to_string(label_width, &value_width, verticalbar_count, true)
)?;
resetln(f)?;
// Body
for 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) -> String
where
B: Borrow<bool>,
I: IntoIterator<Item = B>,
{
format!(
"[{}]",
iter.into_iter()
.map(|b| ['.', '#'][usize::from(*(b.borrow()))])
.collect::<String>(),
)
}
}
// }}}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0