AtCoder Beginner Contest 344 E

https://atcoder.jp/contests/abc344/tasks/abc344_e

双方向リストを作って、それぞれのノードの値とノード自体を辞書にすればいいのですが、ノードをいくつも共有しなければならないので、たぶん参照カウントを使うしかないです。そうすると非常に複雑になって、AIが無いと厳しいですね。

// String Bags
#![allow(non_snake_case)]


//////////////////// library ////////////////////

fn read<T: std::str::FromStr>() -> T {
    let mut line = String::new();
    std::io::stdin().read_line(&mut line).ok();
    line.trim().parse().ok().unwrap()
}

fn read_vec<T: std::str::FromStr>() -> Vec<T> {
    read::<String>().split_whitespace()
            .map(|e| e.parse().ok().unwrap()).collect()
}


//////////////////// Node ////////////////////

use std::cell::RefCell;
use std::collections::HashMap;
use std::rc::Rc;

type Link = Option<Rc<RefCell<Node>>>;

struct Node {
    value: i32,
    prev: Link,
    next: Link,
}

impl Node {
    fn new(v: i32) -> Rc<RefCell<Node>> {
        Rc::new(RefCell::new(Node {
            value: v,
            prev: None,
            next: None,
        }))
    }
}

struct BidirectionalList {
    top: Link,
    dic: HashMap<i32, Link>,
}

impl BidirectionalList {
    fn new(top: Link, dic: HashMap<i32, Link>) -> BidirectionalList {
        BidirectionalList { top, dic }
    }
    
    fn insert(&mut self, x: i32, y: i32) {
        let node = self.dic.get(&x).unwrap().clone();
        let new_node = Node::new(y);
        self.dic.insert(y, Some(Rc::clone(&new_node)));
        new_node.borrow_mut().prev = node.clone();
        let next_node = node.as_ref().unwrap().borrow().next.clone();
        node.as_ref().unwrap().borrow_mut().next = Some(new_node.clone());
        if let Some(next_node) = next_node {
            new_node.borrow_mut().next = Some(next_node.clone());
            next_node.borrow_mut().prev = Some(new_node);
        }
    }
    
    fn remove(&mut self, x: i32) {
        let node_ = self.dic.remove(&x).unwrap();
        let node = node_.as_ref().unwrap();
        let prev_node = node.borrow().prev.clone();
        let next_node = node.borrow().next.clone();
        if let Some(ref prev_node) = prev_node {
            prev_node.borrow_mut().next = next_node.clone();
        } else if let Some(ref next_node) = next_node {
            self.top = Some(next_node.clone());
        }
        if let Some(next_node) = next_node {
            next_node.borrow_mut().prev = prev_node;
        }
    }
    
    fn to_vec(&self) -> Vec<i32> {
        let mut vs = vec![];
        let mut v = self.top.clone();
        while let Some(node) = v {
            vs.push(node.borrow().value);
            v = node.borrow().next.clone();
        }
        vs
    }
    
    fn create(A: Vec<i32>) -> BidirectionalList {
        let N = A.len();
        let nodes: Vec<Link> = A.into_iter().
                                map(|e| Some(Node::new(e))).collect();
        for i in 0..N {
            let mut node = nodes[i].as_ref().unwrap().borrow_mut();
            node.prev = if i == 0 { None } else { nodes[i-1].clone() };
            node.next = if i == N - 1 { None } else { nodes[i+1].clone() };
        }
        let dic: HashMap<i32, Link> = nodes.iter().
                map(|node| (node.as_ref().unwrap().borrow().value,
                                                    node.clone())).collect();
        BidirectionalList::new(nodes[0].clone(), dic)
    }
}


//////////////////// Query ////////////////////

enum Query {
    Insert(i32, i32),
    Remove(i32),
}

impl Query {
    fn read() -> Query {
        let v: Vec<i32> = read_vec();
        if v[0] == 1 {
            Query::Insert(v[1], v[2])
        }
        else {
            Query::Remove(v[1])
        }
    }
}


//////////////////// process ////////////////////

fn read_input() -> (Vec<i32>, usize) {
    let _N: usize = read();
    let A: Vec<i32> = read_vec();
    let Q: usize = read();
    (A, Q)
}

fn F(A: Vec<i32>, Q: usize) {
    let mut blist = BidirectionalList::create(A);
    for _ in 0..Q {
        match Query::read() {
            Query::Insert(x, y) => blist.insert(x, y),
            Query::Remove(x)    => blist.remove(x)
        }
    }
    let v = blist.to_vec();
    println!("{}", v.into_iter().map(|e| e.to_string()).
                            collect::<Vec<_>>().join(" "));
}

fn main() {
    let (A, Q) = read_input();
    F(A, Q)
}