Open tipstar0125 opened 3 months ago
問題:https://atcoder.jp/contests/abc344/tasks/abc344_e 解答:https://atcoder.jp/contests/abc344/submissions/51213421
ライブラリ
#[derive(Debug)] struct LinkedNode { front: Option<usize>, back: Option<usize>, } #[derive(Debug)] struct LinkedList { list: HashMap<usize, LinkedNode>, } impl LinkedList { fn new(v: Vec<usize>) -> Self { let mut list = HashMap::new(); if v.len() == 1 { list.insert( v[0], LinkedNode { front: None, back: None, }, ); } else if v.len() >= 2 { list.insert( v[0], LinkedNode { front: None, back: Some(v[1]), }, ); list.insert( v[v.len() - 1], LinkedNode { front: Some(v[v.len() - 2]), back: None, }, ); for i in 1..v.len() - 1 { list.insert( v[i], LinkedNode { front: Some(v[i - 1]), back: Some(v[i + 1]), }, ); } } LinkedList { list } } fn remove(&mut self, x: usize) { let front = self.list[&x].front; let back = self.list[&x].back; if let Some(front) = front { if let Some(v) = self.list.get_mut(&front) { v.back = back; } } if let Some(back) = back { if let Some(v) = self.list.get_mut(&back) { v.front = front; } } self.list.remove(&x); } // xの直後にyを挿入 fn insert(&mut self, x: usize, y: usize) { self.list.insert( y, LinkedNode { front: Some(x), back: self.list[&x].back, }, ); if let Some(back) = self.list[&x].back { if let Some(v) = self.list.get_mut(&back) { v.front = Some(y); } } if let Some(v) = self.list.get_mut(&x) { v.back = Some(y); } } fn to_list(&self) -> Vec<usize> { let mut ret = vec![]; let mut now = { let mut head = 0; for (k, v) in self.list.iter() { if v.front.is_none() { head = *k; break; } } head }; loop { ret.push(now); if let Some(x) = self.list[&now].back { now = x; } else { break; } } ret } }
問題:https://atcoder.jp/contests/abc344/tasks/abc344_e 解答:https://atcoder.jp/contests/abc344/submissions/51213421
ライブラリ