Cod sursa(job #3266523)

Utilizator lucametehauDart Monkey lucametehau Data 9 ianuarie 2025 09:40:42
Problema Xor Max Scor 80
Compilator rs Status done
Runda Arhiva de probleme Marime 2.34 kb
use std::fs::File;
use std::{io::*};

const MAX_BYTES: usize = 21;

#[derive(Clone)]
struct Node {
    pos: usize,
    children: Vec<Option<Box<Node>>>
}

impl Node {
    fn new() -> Self {
        Node {
            pos: 0,
            children: vec![None; 2]
        }
    }

    fn insert(&mut self, byte: usize, number: i32, pos: usize) {
        if byte == 0 {
            self.pos = pos;
            return;
        }
        let b = ((number >> byte) & 1) as usize;
        if self.children[b].is_none() {
            self.children[b] = Some(Box::new(Node::new()));
        }
        self.children[b].as_mut().unwrap().insert(byte - 1, number, pos);
    }

    fn insert_number(&mut self, number: i32, pos: usize) {
        self.insert(MAX_BYTES, number, pos);
    }

    fn get_best(&self, byte: usize, number: i32) -> usize {
        if byte == 0 { return self.pos; }

        let b = (1 ^ ((number >> byte) & 1)) as usize;
        return if let Some(child) = &self.children[b] { 
            child.get_best(byte - 1, number)
        } else { 
            self.children[1 ^ b].as_ref().unwrap().get_best(byte - 1, number)
        };
    }

    fn get_xor_max_pos(&self, number: i32) -> usize {
        self.get_best(MAX_BYTES, number)
    }
}

fn main() {
    let in_file = File::open("xormax.in").unwrap();
    let out_file = File::create("xormax.out").unwrap();

    let mut input = BufReader::new(in_file);
    let mut output = BufWriter::new(out_file);

    let mut line = String::new();
    input.read_line(&mut line).unwrap();
    let stuff: Vec<usize> = line.split_whitespace().map(|x| x.parse().unwrap()).collect();
    let n = stuff[0];

    line.clear();
    input.read_line(&mut line).unwrap();
    let v: Vec<i32> = line.split_whitespace().map(|x| x.parse().unwrap()).collect();
    let mut xor_sum: Vec<i32> = vec![0; n + 1];
    let mut root = Node::new();

    xor_sum[0] = 0;
    root.insert_number(0, 0);
    let mut mx = 0;
    let mut l = 0;
    let mut r = 0;
    for (i, x) in v.into_iter().enumerate() {
        xor_sum[i + 1] = xor_sum[i] ^ x;
        let pos = root.get_xor_max_pos(xor_sum[i + 1]);
        if xor_sum[i + 1] ^ xor_sum[pos] > mx {
            mx = xor_sum[i + 1] ^ xor_sum[pos];
            l = pos + 1;
            r = i + 1;
        }
        root.insert_number(xor_sum[i + 1], i + 1);
    }
    writeln!(output, "{} {} {}", mx, l, r).unwrap();
}