Pagini recente » Cod sursa (job #2532526) | Cod sursa (job #360605) | Cod sursa (job #3143522) | Cod sursa (job #2090572) | Cod sursa (job #3266523)
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();
}