結果
| 問題 |
No.3147 Parentheses Modification and Rotation (RM Ver.)
|
| コンテスト | |
| ユーザー |
 Kana Nagata
|
| 提出日時 | 2025-05-17 02:22:00 |
| 言語 | Rust (1.83.0 + proconio) |
| 結果 |
AC
|
| 実行時間 | 5 ms / 2,000 ms |
| コード長 | 18,810 bytes |
| コンパイル時間 | 15,337 ms |
| コンパイル使用メモリ | 388,208 KB |
| 実行使用メモリ | 7,844 KB |
| 最終ジャッジ日時 | 2025-05-17 02:22:18 |
| 合計ジャッジ時間 | 14,753 ms |
|
ジャッジサーバーID （参考情報） |
judge2 / judge3 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 2 |
| other | AC * 33 |
コンパイルメッセージ
warning: unused import: `map::hmap`
--> src/main.rs:397:13
|
397 | pub use map::hmap;
| ^^^^^^^^^
|
= note: `#[warn(unused_imports)]` on by default
warning: unused import: `map::vmap`
--> src/main.rs:398:13
|
398 | pub use map::vmap;
| ^^^^^^^^^
warning: unused import: `vec2::vec2`
--> src/main.rs:402:13
|
402 | pub use vec2::vec2;
| ^^^^^^^^^^
warning: unused import: `vecs::hvec`
--> src/main.rs:403:13
|
403 | pub use vecs::hvec;
| ^^^^^^^^^^
warning: unused import: `vecs::vvec`
--> src/main.rs:404:13
|
404 | pub use vecs::vvec;
| ^^^^^^^^^^
ソースコード
use proconio::input;
use std::collections::VecDeque;
fn main() {
input! {
_n: usize,
s: String,
r: i64,
m: i64,
}
let a = s
.chars()
.rev()
.map(|c| match c {
'(' => -1,
')' => 1,
_ => unreachable!(),
})
.collect::<Vec<_>>();
let mut deque = VecDeque::<Event>::new();
let mut start_value = 0;
let mut end_value = 0;
for (i, &x) in a.iter().enumerate() {
end_value += x;
while let Some(&Event { time: _, value }) = deque.front() {
if end_value <= value {
deque.pop_back();
} else {
break;
}
}
deque.push_back(Event {
time: i,
value: end_value,
});
}
let ans = if (end_value - start_value) % 2 == 0 {
std::iter::once((start_value, deque.front().unwrap().value, end_value))
.chain(a.iter().enumerate().map(|(i, &x)| {
start_value += x;
end_value += x;
while let Some(&Event { time, value: _ }) = deque.front() {
if time < i {
deque.pop_front();
} else {
break;
}
}
while let Some(&Event { time: _, value }) = deque.front() {
if end_value <= value {
deque.pop_back();
} else {
break;
}
}
deque.push_back(Event {
time: s.len() + i,
value: end_value,
});
(start_value, deque.front().unwrap().value, end_value)
}))
.enumerate()
.map(|(i, (x, y, z))| ((x - y + 1) / 2 + (z - y + 1) / 2) * m + i as i64 * r)
.min()
.unwrap()
} else {
-1
};
println!("{ans}");
}
#[derive(Debug, Clone, Copy)]
struct Event {
time: usize,
value: i64,
}
// lg {{{
// https://ngtkana.github.io/ac-adapter-rs/lg/index.html
#[allow(dead_code)]
mod lg {
mod map {
use crate::lg::align_of;
use crate::lg::format;
use crate::lg::table::Align;
use crate::lg::table::Cell;
use crate::lg::table::Table;
use std::collections;
use std::collections::BTreeMap;
use std::collections::HashMap;
use std::fmt;
use std::iter;
use std::slice;
use std::vec;
pub fn vmap<'a, K, V, M>(title: &str, map: M) -> Table
where
M: Copy + Map<'a, K = K, V = V>,
K: fmt::Debug,
V: fmt::Debug,
{
Table {
table: iter::once(vec![
Cell {
text: String::new(),
align: Align::Left,
},
Cell {
text: title.to_string(),
align: Align::Center,
},
])
.chain(map.map_iter().map(|(k, v)| {
let v = format(&v);
vec![
Cell {
text: format(&k),
align: Align::Center,
},
Cell {
align: align_of(&v),
text: v,
},
]
}))
.collect(),
}
}
pub fn hmap<'a, K, V, M>(title: &str, map: M) -> Table
where
M: Copy + Map<'a, K = K, V = V>,
K: fmt::Debug,
V: fmt::Debug,
{
Table {
table: vec![
iter::once(Cell {
text: String::new(),
align: Align::Left,
})
.chain(map.map_iter().map(|(k, _)| Cell {
text: format(&k),
align: Align::Center,
}))
.collect(),
iter::once(Cell {
text: title.to_string(),
align: Align::Left,
})
.chain(map.map_iter().map(|(_, v)| {
let v = format(&v);
Cell {
align: align_of(&v),
text: v,
}
}))
.collect(),
],
}
}
pub fn deconstruct_ref_tuple<K, V>((k, v): &(K, V)) -> (&K, &V) {
(k, v)
}
pub trait Map<'a>: 'a {
type K;
type V;
type I: Iterator<Item = (&'a Self::K, &'a Self::V)>;
fn map_iter(self) -> Self::I;
}
impl<'a, K, V, S> Map<'a> for &'a HashMap<K, V, S> {
type I = collections::hash_map::Iter<'a, K, V>;
type K = K;
type V = V;
fn map_iter(self) -> Self::I {
self.iter()
}
}
impl<'a, K, V> Map<'a> for &'a BTreeMap<K, V> {
type I = collections::btree_map::Iter<'a, K, V>;
type K = K;
type V = V;
fn map_iter(self) -> Self::I {
self.iter()
}
}
impl<'a, K, V> Map<'a> for &'a [(K, V)] {
type I = iter::Map<slice::Iter<'a, (K, V)>, fn(&(K, V)) -> (&K, &V)>;
type K = K;
type V = V;
fn map_iter(self) -> Self::I {
self.iter().map(deconstruct_ref_tuple)
}
}
impl<'a, K, V> Map<'a> for &'a Vec<(K, V)> {
type I = iter::Map<slice::Iter<'a, (K, V)>, fn(&(K, V)) -> (&K, &V)>;
type K = K;
type V = V;
fn map_iter(self) -> Self::I {
self.iter().map(deconstruct_ref_tuple)
}
}
impl<'a, const N: usize, K, V> Map<'a> for &'a [(K, V); N] {
type I = iter::Map<slice::Iter<'a, (K, V)>, fn(&(K, V)) -> (&K, &V)>;
type K = K;
type V = V;
fn map_iter(self) -> Self::I {
self.iter().map(deconstruct_ref_tuple)
}
}
}
mod table {
use core::fmt;
const GRAY: &str = "\x1b[48;2;127;127;127;37m";
const RESET: &str = "\x1b[0m";
pub struct Table {
pub table: Vec<Vec<Cell>>,
}
pub struct Cell {
pub text: String,
pub align: Align,
}
pub enum Align {
Left,
Center,
Right,
}
impl fmt::Display for Table {
fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
struct ColumnFormat<'a> {
pre: &'a str,
width: usize,
post: &'a str,
}
let Self { table } = self;
let w = table[0].len();
assert!(table.iter().all(|row| row.len() == w));
let column_format = (0..w)
.map(|j| ColumnFormat {
pre: " ",
width: table
.iter()
.map(|row| row[j].text.len().max(1))
.max()
.unwrap(),
post: if j == 0 { " │" } else { " " },
})
.collect::<Vec<_>>();
for (i, row) in table.iter().enumerate() {
if i == 0 {
write!(f, "{GRAY}")?;
}
for (&ColumnFormat { pre, width, post }, Cell { text, align }) in
column_format.iter().zip(row)
{
write!(f, "{pre}")?;
match align {
Align::Left => write!(f, "{text:<width$}")?,
Align::Center => write!(f, "{text:^width$}")?,
Align::Right => write!(f, "{text:>width$}")?,
}
write!(f, "{post}")?;
}
if i == 0 {
write!(f, "{RESET}")?;
}
writeln!(f)?;
}
Ok(())
}
}
}
mod vec2 {
use crate::lg::align_of;
use crate::lg::format;
use crate::lg::table::Align;
use crate::lg::table::Cell;
use crate::lg::table::Table;
use std::fmt;
use std::iter;
pub fn vec2<'a, T, R, S>(title: &str, vec2: &'a S) -> Table
where
T: fmt::Debug + 'a,
R: ?Sized,
&'a R: Copy + IntoIterator<Item = &'a T> + 'a,
&'a S: Copy + IntoIterator<Item = &'a R>,
{
let w = vec2
.into_iter()
.map(|row| row.into_iter().count())
.max()
.unwrap();
Table {
table: iter::once(
iter::once(Cell {
text: title.to_string(),
align: Align::Left,
})
.chain((0..w).map(|i| Cell {
text: i.to_string(),
align: Align::Center,
}))
.collect(),
)
.chain(vec2.into_iter().enumerate().map(|(j, row)| {
iter::once(Cell {
text: j.to_string(),
align: Align::Center,
})
.chain(row.into_iter().map(|v| {
let v = format(&v);
Cell {
align: align_of(&v),
text: v,
}
}))
.chain(iter::repeat_with(|| Cell {
text: String::new(),
align: Align::Left,
}))
.take(1 + w)
.collect()
}))
.collect(),
}
}
}
mod vecs {
use super::table::Cell;
use super::table::Table;
use crate::lg::align_of;
use crate::lg::table::Align;
use std::iter;
pub fn hvec(vecs: &[(String, Vec<String>)]) -> Table {
let w = vecs.iter().map(|(_, row)| row.len()).max().unwrap();
Table {
table: iter::once(
iter::once(Cell {
text: String::new(),
align: Align::Left,
})
.chain((0..w).map(|i| Cell {
text: i.to_string(),
align: Align::Center,
}))
.collect(),
)
.chain(vecs.iter().map(|(title, row)| {
iter::once(Cell {
text: title.to_string(),
align: Align::Center,
})
.chain(row.iter().map(|v| Cell {
align: align_of(v),
text: v.clone(),
}))
.chain(iter::repeat_with(|| Cell {
text: String::new(),
align: Align::Left,
}))
.take(1 + w)
.collect()
}))
.collect(),
}
}
pub fn vvec(vecs: &[(String, Vec<String>)]) -> Table {
let h = vecs.iter().map(|(_, col)| col.len()).max().unwrap();
Table {
table: iter::once(
iter::once(Cell {
text: String::new(),
align: Align::Center,
})
.chain(vecs.iter().map(|(title, _)| Cell {
text: title.to_string(),
align: Align::Center,
}))
.collect(),
)
.chain((0..h).map(|i| {
iter::once(Cell {
text: i.to_string(),
align: Align::Center,
})
.chain(vecs.iter().map(|(_, vec)| {
let v = vec.get(i).map_or("", String::as_str);
Cell {
align: align_of(v),
text: v.to_string(),
}
}))
.collect()
}))
.collect(),
}
}
}
pub use map::hmap;
pub use map::vmap;
use std::borrow::Borrow;
use std::fmt;
use table::Align;
pub use vec2::vec2;
pub use vecs::hvec;
pub use vecs::vvec;
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>(),
)
}
pub fn align_of(s: &str) -> Align {
// To improve this: https://doc.rust-lang.org/reference/tokens.html#floating-point-literals
match s.parse::<f64>() {
Ok(_) => Align::Right,
Err(_) => Align::Left,
}
}
#[macro_export]
macro_rules! lg {
(@contents $head:expr $(, $tail:expr)*) => {{
$crate::__lg_internal!($head);
$(
eprint!(",");
$crate::__lg_internal!($tail);
)*
eprintln!();
}};
($($expr:expr),* $(,)?) => {{
eprint!("{} \u{276f}", line!());
$crate::lg!(@contents $($expr),*)
}};
}
#[doc(hidden)]
#[macro_export]
macro_rules! __lg_internal {
($value:expr) => {{
match $value {
head => {
eprint!(" {} = {}", stringify!($value), $crate::lg::format(&head));
}
}
}};
}
#[macro_export]
macro_rules! table {
($vec2:expr) => {
eprint!(
"{}",
$crate::lg::vec2($crate::lg::remove_ampersand(stringify!($vec2)), $vec2)
);
};
}
#[macro_export]
macro_rules! vmap {
($map:expr) => {
eprint!(
"{}",
$crate::lg::vmap($crate::lg::remove_ampersand(stringify!($map)), $map)
);
};
}
#[macro_export]
macro_rules! hmap {
($map:expr) => {
eprint!(
"{}",
$crate::lg::hmap($crate::lg::remove_ampersand(stringify!($map)), $map)
);
};
}
#[macro_export]
macro_rules! vvec {
($($(@field $field:ident)* $vecs:expr),+ $(,)?) => {
let mut vecs = Vec::new();
$(
let name = $crate::lg::remove_ampersand(stringify!($vecs));
#[allow(unused_mut, unused_assignments)]
let mut has_field = false;
$(
#[allow(unused_mut, unused_assignments)]
{
let mut name = name.to_owned();
has_field = true;
name.push_str(".");
name.push_str(stringify!($field));
let values = (&$vecs).into_iter().map(|v| $crate::lg::format(&v.$field)).collect::<Vec<_>>();
vecs.push((name, values))
}
)*
if !has_field {
let values = (&$vecs).into_iter().map(|v| $crate::lg::format(&v)).collect::<Vec<_>>();
vecs.push((name.to_owned(), values))
}
)+
eprint!("{}", $crate::lg::vvec(&vecs));
};
}
#[macro_export]
macro_rules! hvec {
($($(@field $field:ident)* $vecs:expr),+ $(,)?) => {
let mut vecs = Vec::new();
$(
let name = $crate::lg::remove_ampersand(stringify!($vecs));
#[allow(unused_mut, unused_assignments)]
let mut has_field = false;
$(
#[allow(unused_mut, unused_assignments)]
{
let mut name = name.to_owned();
has_field = true;
name.push_str(".");
name.push_str(stringify!($field));
let values = (&$vecs).into_iter().map(|v| $crate::lg::format(&v.$field)).collect::<Vec<_>>();
vecs.push((name, values))
}
)*
if !has_field {
let values = (&$vecs).into_iter().map(|v| $crate::lg::format(&v)).collect::<Vec<_>>();
vecs.push((name.to_owned(), values))
}
)+
eprint!("{}", $crate::lg::hvec(&vecs));
};
}
pub fn remove_ampersand(mut s: &str) -> &str {
while let Some(t) = s.strip_prefix('&') {
s = t;
}
s
}
pub fn format<T: fmt::Debug>(t: &T) -> String {
let s = format!("{t:?}")
.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("true", "#")
.replace("false", ".");
let mut s = s.as_str();
while s.starts_with("Some(") {
s = s.strip_prefix("Some(").unwrap();
s = s.strip_suffix(')').unwrap();
}
while s.len() > 2 && s.starts_with('"') && s.ends_with('"') {
s = s.strip_prefix('"').unwrap();
s = s.strip_suffix('"').unwrap();
}
s.to_owned()
}
}
// }}}