https://atcoder.jp/contests/abc344/tasks/abc344_e
双方向リストを作って、それぞれのノードの値とノード自体を辞書にすればいいのですが、ノードをいくつも共有しなければならないので、たぶん参照カウントを使うしかないです。そうすると非常に複雑になって、AIが無いと厳しいですね。
#![allow(non_snake_case)]
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()
}
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)
}
}
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])
}
}
}
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)
}
