Cod sursa(job #3313646)

Utilizator game_difficultyCalin Crangus game_difficulty Data 5 octombrie 2025 18:27:13
Problema Radix Sort Scor 0
Compilator rs Status done
Runda Arhiva educationala Marime 1.67 kb
use std::{fs::File, io::BufWriter, vec};
#[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>) {
    _sort(v, 0);
}

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();
    }
}