Cod sursa(job #3197280)

Utilizator Radu_MocanasuMocanasu Radu Radu_Mocanasu Data 26 ianuarie 2024 13:55:15
Problema Radix Sort Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.92 kb
#include <bits/stdc++.h>
#define base 255
using namespace std;
ifstream fin("radixsort.in");
ofstream fout("radixsort.out");
int v[10000002];
int v2[10000002];
int f[256];
int n;
void count_sort(int p){
    for(int i = 1; i <= n; i++) f[(v[i] >> p) & base]++;
    for(int i = 1; i <= base; i++) f[i] += f[i - 1];
    for(int i = n; i >= 1; i--){
        v2[f[(v[i] >> p) & base]] = v[i];
        f[(v[i] >> p) & base]--;
    }
    for(int i = 1; i <= n; i++) v[i] = v2[i];
}
void radix_sort256(int M){
    int p = 0;
    while(M){
        p += 16;
        M >>= 16;
    }
    for(int i = 0; i <= p; i += 16) count_sort(i);
}
int main()
{
    int a,b,c,i;
    fin >> n >> a >> b >> c;
    v[1] = b;
    int M = b;
    for(i = 1; i <= n; i++){
        v[i] = (a * v[i - 1] + b) % c;
        M = max(M, v[i]);
    }
    radix_sort256(M);
    for(i = 1; i <= n; i += 10) fout << v[i] << " ";
    return 0;
}