Pagini recente » Cod sursa (job #3323614) | Cod sursa (job #3321753) | Cod sursa (job #3313648) | Cod sursa (job #3312172) | Cod sursa (job #3313649)
use std::{fs::File, io::BufWriter};
#[allow(unused_imports)]
use std::io::{BufRead, BufReader, Read, Write};
const FILE: &'static str = "radixsort";
const MAX_DIGITS: usize = 4;
const BASE: usize = 0x100;
const BASE_DIGITS: usize = 8;
fn _sort(v: &mut Vec<u32>, digit: usize) {
if digit >= MAX_DIGITS { return; }
let pattern = (BASE - 1) << (BASE_DIGITS * digit);
let mut cat = vec![0_u32; BASE];
let digit = |x: u32| {
((x as usize & pattern) >> (BASE_DIGITS * digit)) as usize
};
for &x in v.iter() {
cat[digit(x)] += 1;
}
for i in 1..BASE {
cat[i] += cat[i - 1];
}
for i in (1..BASE).rev() {
cat[i] = cat[i - 1];
}
cat[0] = 0;
let mut v2 = vec![0_u32; v.len()];
let mut cnt = vec![0_u32; BASE];
for &x in v.iter() {
v2[(cat[digit(x)] + cnt[digit(x)]) as usize] = x;
cnt[digit(x)] += 1;
}
v.copy_from_slice(&v2);
}
fn sort(v: &mut Vec<u32>) {
for i in 0..MAX_DIGITS {
_sort(v, i);
}
}
fn main() {
let mut fin = BufReader::new(File::open(format!("{}.in", FILE)).unwrap());
let mut fout = BufWriter::new(File::create(format!("{}.out", FILE)).unwrap());
let mut input = String::new();
fin.read_line(&mut input).unwrap();
let [n, a, b, c] = input.trim().split_ascii_whitespace().map(|x| x.parse::<usize>().unwrap()).collect::<Vec<usize>>()[..] else {
panic!("Incorrect input shape");
};
let a = a as u64;
let b = b as u64;
let c = c as u64;
let mut v = vec![0_u32; n];
v[0] = b as u32;
for i in 1..n {
v[i] = ((a * (v[i - 1] as u64) + b) % c) as u32;
}
sort(&mut v);
for i in (0..n).step_by(10) {
write!(&mut fout, "{} ", v[i]).unwrap();
}
}