Pagini recente » Cod sursa (job #2295576) | Cod sursa (job #708741) | Cod sursa (job #2878282) | Cod sursa (job #2899405) | Cod sursa (job #3311983)
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();
}