Cod sursa(job #3311983)

Utilizator sad_carrotVisan Sebastian sad_carrot Data 25 septembrie 2025 10:56:06
Problema Schi Scor 100
Compilator rs Status done
Runda Arhiva de probleme Marime 3.23 kb
use std::{
    cmp::{
        Ordering::{Equal, Greater, Less},
        min,
    },
    fs,
    usize::MAX,
};

struct Node {
    value: usize,
    minimum: usize, // of the subtree
    raise: usize,   // raise the minimum of the entire subtree
    pos: usize,
    left: Subtree,
    right: Subtree,
}

struct Subtree(Option<Box<Node>>);

impl Subtree {
    pub fn new(nums: &[usize], before: usize) -> Self {
        if nums.is_empty() {
            Subtree(None)
        } else {
            let middle = nums.len() / 2;
            let left = Subtree::new(&nums[..middle], before);
            let right = Subtree::new(&nums[middle + 1..], before + middle + 1);
            Subtree(Some(Box::new(Node {
                value: nums[middle],
                minimum: min(nums[middle], min(left.min(), right.min())),
                raise: 0,
                pos: before + middle,
                left,
                right,
            })))
        }
    }
    pub fn min(&self) -> usize {
        match &self.0 {
            None => MAX,
            Some(node) => {
                if node.minimum == MAX {
                    node.minimum
                } else {
                    node.minimum + node.raise
                }
            }
        }
    }
    // right-most minimum
    pub fn query(&self, k: usize) -> usize {
        match &self.0 {
            None => panic!(),
            Some(node) => {
                if node.right.min() == k - node.raise {
                    node.right.query(k - node.raise)
                } else {
                    if node.value == k - node.raise {
                        node.pos
                    } else {
                        node.left.query(k - node.raise)
                    }
                }
            }
        }
    }
    pub fn plus_min(&mut self) {
        match &mut self.0 {
            None => {}
            Some(node) => node.raise += 1,
        }
    }
    // remove (set max) node at pos and +1 all nodes on its left
    pub fn update(&mut self, pos: usize) {
        match &mut self.0 {
            None => {}
            Some(node) => {
                match node.pos.cmp(&pos) {
                    Equal => {
                        node.value = MAX;
                        node.left.plus_min();
                    }
                    Less => {
                        node.right.update(pos);
                        if node.value < MAX {
                            node.value += 1;
                        }
                        node.left.plus_min();
                    }
                    Greater => node.left.update(pos),
                };
                node.minimum = min(node.value, min(node.left.min(), node.right.min()));
            }
        }
    }
}

fn main() {
    let input = fs::read_to_string("schi.in").unwrap();
    let content = input
        .split_ascii_whitespace()
        .map(|s| s.parse::<usize>().unwrap())
        .collect::<Vec<usize>>();
    let n = content[0];
    let nums = &content[1..];

    let mut arbint = Subtree::new(nums, 0);

    let output: String = (1..n + 1)
        .map(|i| {
            let pos = arbint.query(i);
            arbint.update(pos);
            format!("{}\n", pos + 1)
        })
        .collect();
    fs::write("schi.out", output).unwrap();
}