Pagini recente » Borderou de evaluare (job #3322521) | Cod sursa (job #3342205) | Cod sursa (job #3302284) | Cod sursa (job #3320277) | Cod sursa (job #3313647)
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<usize>, digit: usize) {
if digit >= MAX_DIGITS { return; }
let pattern = (BASE - 1) << (BASE_DIGITS * digit);
let mut cat = vec![0_usize; BASE];
for x in v.iter() {
cat[(x & pattern) >> (BASE_DIGITS * digit)] += 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_usize; v.len()];
let mut cnt = vec![0_usize; BASE];
for &x in v.iter() {
let digit = (x & pattern) >> (BASE_DIGITS * digit);
v2[cat[digit] + cnt[digit]] = x;
cnt[digit] += 1;
}
v.copy_from_slice(&v2);
}
fn sort(v: &mut Vec<usize>) {
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 usize;
let b = b as usize;
let c = c as usize;
let mut v = vec![0_usize; n];
v[0] = b;
for i in 1..n {
v[i] = (a * v[i - 1] + b) % c;
}
sort(&mut v);
for i in (0..n).step_by(10) {
write!(&mut fout, "{} ", v[i]).unwrap();
}
}