Submit Info #30428

Problem Lang User Status Time Memory
Persistent Queue rust sansen AC 400 ms 93.23 MiB

ケース詳細
Name Status Time Memory
ephemeral_00 AC 216 ms 75.00 MiB
example_00 AC 0 ms 0.62 MiB
half_rot_killer_00 AC 235 ms 80.81 MiB
random_00 AC 400 ms 79.19 MiB
random_01 AC 400 ms 93.23 MiB
random_02 AC 32 ms 11.30 MiB
random_2_00 AC 310 ms 76.29 MiB
random_2_01 AC 371 ms 89.04 MiB
random_2_02 AC 30 ms 10.99 MiB
random_3_00 AC 194 ms 63.10 MiB
random_3_01 AC 206 ms 75.14 MiB
random_3_02 AC 22 ms 9.05 MiB
two_stacks_killer_00 AC 205 ms 77.91 MiB

use std::cell::*; use std::rc::*; #[derive(Debug)] enum Lazy<T> { Reverse(List<T>), Concat(List<T>, List<T>), Cons(Rc<T>, List<T>), Nil, } impl<T> Lazy<T> { fn to_list(self) -> List<T> { List(Rc::new(RefCell::new(self))) } } impl<T> Clone for Lazy<T> { fn clone(&self) -> Self { match self { Lazy::Nil => Lazy::Nil, Lazy::Cons(a, b) => Lazy::Cons(a.clone(), b.clone()), _ => unreachable!("can't clone Reverse or Concat"), } } } #[derive(Debug)] struct List<T>(Rc<RefCell<Lazy<T>>>); impl<T> Clone for List<T> { fn clone(&self) -> Self { List(self.0.clone()) } } impl<T> List<T> { fn new() -> Self { List(Rc::new(RefCell::new(Lazy::Nil))) } fn eval(&self) { let po = &mut *self.0.borrow_mut(); match po { Lazy::Reverse(x) => { let mut list = Lazy::Nil; let mut x = x.0.clone(); while let Lazy::Cons(ref a, ref b) = *x.clone().borrow() { list = Lazy::Cons(a.clone(), list.to_list()); x = b.0.clone(); } *po = list; } Lazy::Concat(a, b) => { a.eval(); let res = match &*a.0.borrow() { Lazy::Nil => { b.eval(); b.0.borrow().clone() }, Lazy::Cons(p, q) => { Lazy::Cons(p.clone(), Lazy::Concat(q.clone(), b.clone()).to_list()) }, _ => unreachable!(), }; *po = res; } _ => (), } } fn tail(&self) -> Self { self.eval(); match &*self.0.borrow() { Lazy::Cons(_, b) => b.clone(), _ => List::new(), } } } impl<T: Clone> List<T> { fn head(&self) -> Option<T> { self.eval(); match &*self.0.borrow() { Lazy::Cons(a, _) => Some((**a).clone()), _ => None, } } } #[derive(Debug)] struct Queue<T> { front: List<T>, back: List<T>, f_size: usize, t_size: usize, } impl<T> Queue<T> { fn new() -> Self { Queue { front: Lazy::Nil.to_list(), back: Lazy::Nil.to_list(), f_size: 0, t_size: 0, } } fn fix(self) -> Self { if self.f_size >= self.t_size { return self; } let mut q = self; q.f_size += q.t_size; q.t_size = 0; q.front = Lazy::Concat(q.front, Lazy::Reverse(q.back.clone()).to_list()).to_list(); q.back = List::new(); q } fn push(&self, val: T) -> Self { Queue { front: self.front.clone(), back: Lazy::Cons(Rc::new(val), self.back.clone()).to_list(), f_size: self.f_size, t_size: self.t_size + 1, }.fix() } fn pop(&self) -> Self { if self.f_size == 0 { return Queue::new(); } Queue { front: self.front.tail(), back: self.back.clone(), f_size: self.f_size - 1, t_size: self.t_size, }.fix() } } impl<T: Clone> Queue<T> { fn top(&self) -> Option<T> { self.front.head() } } use std::io::Read; use std::io::Write; fn run() { let out = std::io::stdout(); let mut out = std::io::BufWriter::new(out.lock()); let mut s = String::new(); std::io::stdin().read_to_string(&mut s).unwrap(); let mut it = s.trim().split_whitespace(); let q: i32 = it.next().unwrap().parse().unwrap(); let mut map = std::collections::BTreeMap::<i32, Queue<u32>>::new(); map.insert(-1, Queue::new()); for i in 0..q { let op: usize = it.next().unwrap().parse().unwrap(); let t: i32 = it.next().unwrap().parse().unwrap(); let que = map.get(&t).unwrap(); let res = if op == 0 { let x: u32 = it.next().unwrap().parse().unwrap(); que.push(x) } else { if let Some(ans) = que.top() { writeln!(out, "{}", ans).ok(); que.pop() } else { unreachable!(); } }; map.insert(i, res); } } fn main() { run(); }