Cod sursa(job #3228736)

Utilizator andreioneaAndrei Onea andreionea Data 10 mai 2024 20:04:02
Problema Heapuri cu reuniune Scor 100
Compilator rs Status done
Runda Arhiva educationala Marime 3.82 kb
use std::{
    fs::File,
    io::{BufRead, BufReader, BufWriter, Write},
};

#[derive(Debug, Clone)]
struct PairingHeap {
    top: Option<u32>,
    sub_heaps: Vec<PairingHeap>,
}

impl PairingHeap {   
    fn is_empty(&self) -> bool {
        self.top.is_none() && self.sub_heaps.is_empty()
    }

    fn max(&mut self) -> Option<u32> {
        let val = self.top.take();
        let mut sub_heaps = vec![];
        std::mem::swap(&mut sub_heaps,&mut self.sub_heaps);
        while !sub_heaps.is_empty() {
            let child = sub_heaps.pop();
            if let Some(child) = child {
                let mut child = child;
                self.meld(&mut child);
            }
        }
        val
    }
    fn meld(&mut self, other: &mut PairingHeap) {
        if other.is_empty() {
            return;
        }
        if self.is_empty() {
            self.top = other.top;
            std::mem::swap(&mut self.sub_heaps, &mut other.sub_heaps);
            return;
        }
        if self.top.unwrap() >= other.top.unwrap() {
            let other_top = other.top.take();
            let mut other_sub_heaps = vec![];
            std::mem::swap(&mut other_sub_heaps, &mut other.sub_heaps);
            self.sub_heaps.push(PairingHeap {
                top: other_top,
                sub_heaps: other_sub_heaps
            });
        } else {
            let old_top = self.top.take();
            self.top = other.top.take();
            let mut old_sub_heaps = vec![];
            std::mem::swap(&mut old_sub_heaps, &mut self.sub_heaps);
            let old_self = PairingHeap {
                top: old_top,
                sub_heaps: old_sub_heaps,
            };
            std::mem::swap(&mut self.sub_heaps, &mut other.sub_heaps);
            self.sub_heaps.push(old_self);
        }
    }
    fn insert(&mut self, element: u32) {
        let mut other = PairingHeap {
            top: Some(element),
            sub_heaps: vec![],
        };
        self.meld(&mut other);
    }
}

fn main() {
    let mut input_file = BufReader::new(File::open("mergeheap.in").unwrap());
    let mut current_line = String::new();
    let _ = input_file.read_line(&mut current_line).unwrap();
    let (n, q) = current_line.trim().split_once(' ').unwrap();
    let n = n.parse::<u32>().unwrap();
    let q = q.parse::<u32>().unwrap();
    let mut ph: Vec<PairingHeap> = vec![
        PairingHeap {
            top: None,
            sub_heaps: vec![]
        };
        n as usize
    ];
    let mut out_file = BufWriter::new(File::create("mergeheap.out").unwrap());
    for _ in 0..q {
        current_line.clear();
        let _ = input_file.read_line(&mut current_line).unwrap();
        let (op, rest) = current_line.trim().split_once(' ').unwrap();
        match op {
            "1" => {
                let (m, x) = rest.split_once(' ').unwrap();
                let m = m.parse::<usize>().unwrap();
                let x = x.parse::<u32>().unwrap();
                ph[m - 1].insert(x);
            }
            "2" => {
                let m = rest.parse::<usize>().unwrap();
                let val = ph[m - 1].max().unwrap();
                let _ = writeln!(out_file, "{val}").unwrap();
            }
            "3" => {
                let (a, b) = rest.split_once(' ').unwrap();
                let a = a.parse::<usize>().unwrap();
                let b = b.parse::<usize>().unwrap();
                // Can't do two mutable borrows at the same time from a vector :sadcat:
                if a < b {
                    let (aa, bb) = ph.split_at_mut(b - 1);
                    aa[a - 1].meld(&mut bb[0]);
                } else if a > b {
                    let (aa, bb) = ph.split_at_mut(a - 1);
                    bb[0].meld(&mut aa[b - 1]);
                } else {
                    // WAT
                }
            }
            _ => panic!("Unknown op {op}"),
        }
    }
}