Cod sursa(job #3313648)

Utilizator game_difficultyCalin Crangus game_difficulty Data 5 octombrie 2025 18:36:36
Problema Radix Sort Scor 30
Compilator rs Status done
Runda Arhiva educationala Marime 1.72 kb
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 u32;
    let b = b as u32;
    let c = c as u32;

    
    let mut v = vec![0_u32; 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();
    }
}