Submit Info #60931

Problem Lang User Status Time Memory
Persistent Queue rust Haar AC 329 ms 93.37 MiB

ケース詳細
Name Status Time Memory
ephemeral_00 AC 208 ms 56.15 MiB
example_00 AC 0 ms 0.42 MiB
half_rot_killer2_00 AC 212 ms 86.96 MiB
half_rot_killer_00 AC 226 ms 64.30 MiB
random_00 AC 230 ms 63.45 MiB
random_01 AC 264 ms 75.19 MiB
random_02 AC 23 ms 8.98 MiB
random_2_00 AC 271 ms 76.21 MiB
random_2_01 AC 329 ms 90.33 MiB
random_2_02 AC 26 ms 10.57 MiB
random_3_00 AC 213 ms 75.76 MiB
random_3_01 AC 257 ms 89.96 MiB
random_3_02 AC 26 ms 10.65 MiB
two_stacks_killer_00 AC 314 ms 93.37 MiB

#[allow(unused_imports)] use std::io::{Read, Write}; #[allow(unused_macros)] macro_rules! get { ( $in:ident, [$a:tt; $num:expr] ) => { { let n = $num; (0 .. n).map(|_| get!($in, $a)).collect::<Vec<_>>() } }; ( $in:ident, ($($type:ty),*) ) => { ($(get!($in, $type)),*) }; ( $in:ident, $type:ty ) => { { let token = $in.next().unwrap(); token.parse::<$type>().expect( format!("cannot convert \"{}\" into {}", token, stringify!($type)).as_str() ) } }; } #[allow(unused_macros)] macro_rules! input { ( @inner $in:ident, mut $name:ident : $type:tt ) => { let mut $name = get!($in, $type); }; ( @inner $in:ident, $name:ident : $type:tt ) => { let $name = get!($in, $type); }; ( $in:ident, $($($names:ident)* : $type:tt),* ) => { $( input!(@inner $in, $($names)* : $type); )* } } pub trait JoinStr { fn join_str(&self, _: &str) -> String; } impl<T: std::fmt::Display> JoinStr for Vec<T> { fn join_str(&self, s: &str) -> String { (&self.iter().map(|x| format!("{}", x)).collect::<Vec<_>>()).join(s) } } macro_rules! impl_join_str_tuple { ( $head:ident ) => { impl<$head: std::fmt::Display> JoinStr for ($head,) { #[allow(non_snake_case, redundant_semicolons)] fn join_str(&self, _: &str) -> String { let (ref $head,) = *self; format!("{}", $head) } } }; ( $head:ident, $($tail:ident),+ ) => { impl<$head: std::fmt::Display, $($tail: std::fmt::Display),+> JoinStr for ($head, $($tail),*) { #[allow(non_snake_case, redundant_semicolon)] fn join_str(&self, s: &str) -> String { let mut ret = vec![]; let (ref $head, $(ref $tail,)+) = *self; ret.push(format!("{}", $head)); $( ret.push(format!("{}", $tail)); )+; ret.join_str(s) } } impl_join_str_tuple!($($tail),+); } } impl_join_str_tuple!(T0, T1, T2, T3, T4, T5, T6, T7, T8, T9, T10, T11); #[allow(unused_macros)] macro_rules! io { ( $in:ident, $out:ident ) => { let mut s = String::new(); std::io::stdin().read_to_string(&mut s).unwrap(); let mut $in = s.split_ascii_whitespace(); let $out = std::io::stdout(); let mut $out = std::io::BufWriter::new($out.lock()); }; } #[macro_export] macro_rules! mul_vec { ( $v:expr; $n:expr ) => { vec![$v; $n] }; ( $v:expr; $n:expr, $($ns:expr),+ ) => { vec![mul_vec![$v; $($ns),+]; $n] } } pub mod main { use super::*; use haar_lib::ds::persistent_queue::*; #[derive(Clone, Default)] pub struct Problem {/* write variables here */} impl Problem { pub fn main(&mut self) -> Result<(), Box<dyn std::error::Error>> { io!(cin, cout); input!(cin, q: usize); let mut pqs: Vec<PersistentQueue<u64>> = vec![]; for _ in 0..q { input!(cin, ty: usize); if ty == 0 { input!(cin, t: isize, x: u64); if t == -1 { pqs.push(PersistentQueue::new(x)); } else { pqs.push(pqs[t as usize].push(x)); } } else { input!(cin, t: usize); writeln!(cout, "{:?}", pqs[t].front().unwrap())?; let a = pqs[t].pop().unwrap(); pqs.push(a); } } Ok(()) } /* write functions here */ } } fn main() { main::Problem::default().main().unwrap(); } use crate as haar_lib; pub mod ds { pub mod persistent_queue { use std::rc::Rc; const MAX_SIZE_2: usize = 20; struct Node<T> { value: T, ancestors: Vec<Option<Rc<Node<T>>>>, depth: usize, } impl<T> Node<T> { fn new(value: T) -> Self { Self { value, ancestors: vec![None; MAX_SIZE_2], depth: 0, } } } #[derive(Default)] pub struct PersistentQueue<T> { front_back_node: Option<(Rc<Node<T>>, Rc<Node<T>>)>, } impl<T> PersistentQueue<T> { pub fn new(value: T) -> Self { let node = Node::new(value); let p = Rc::new(node); Self { front_back_node: Some((p.clone(), p.clone())), } } pub fn push(&self, value: T) -> Self { match self.front_back_node.clone() { None => { let p = Rc::new(Node::new(value)); Self { front_back_node: Some((p.clone(), p)), } } Some((front_node, back_node)) => { let mut t = Node::new(value); t.depth = back_node.depth + 1; t.ancestors[0] = Some(back_node); for i in 1..MAX_SIZE_2 { let s = t.ancestors[i - 1].as_ref(); match s { None => { break; } Some(s) => t.ancestors[i] = s.ancestors[i - 1].clone(), } } Self { front_back_node: Some((front_node, Rc::new(t))), } } } } pub fn pop(&self) -> Option<Self> { match self.front_back_node.clone() { None => None, Some((front_node, back_node)) => { if front_node.depth == back_node.depth { Some(Self { front_back_node: None, }) } else { let mut d = back_node.depth - front_node.depth - 1; let mut t = back_node.clone(); for i in (0..MAX_SIZE_2).rev() { if d >= (1 << i) { d -= 1 << i; t = t.ancestors[i].as_ref().unwrap().clone(); } if d == 0 { break; } } Some(Self { front_back_node: Some((t, back_node.clone())), }) } } } } pub fn front(&self) -> Option<&T> { self.front_back_node.as_ref().map(|(t, _)| &t.value) } pub fn back(&self) -> Option<&T> { self.front_back_node.as_ref().map(|(_, t)| &t.value) } pub fn is_empty(&self) -> bool { self.front_back_node.is_none() } pub fn len(&self) -> usize { self.front_back_node .as_ref() .map_or(0, |(f, b)| b.depth - f.depth + 1) } } } }