Cod sursa(job #1972856)

Utilizator GeorginskyGeorge Georginsky Data 23 aprilie 2017 20:45:19
Problema Radix Sort Scor 30
Compilator cpp Status done
Runda Arhiva educationala Marime 0.71 kb
#include <iostream>
#include <fstream>
#include <cstring>
#define B 256
const int N=1e7;
using namespace std;
ifstream in("radixsort.in");
ofstream out("radixsort.out");
int v[N], f[B], w[N];
int main(){
    int n, a, b, c, p, nr=1;
    in>>n>>a>>b>>c;
    v[1]=b;
    for(int i=2; i<=n; i++)v[i]=((long long)v[i-1]*a+b)%c;
    int x=0;
    for(int l=0; l<=3; l++){
        memset(f, 0, sizeof(f));
        for(int i=1; i<=n; i++)f[(v[i]>>x)%B]++;
        for(int i=1; i<=B-1; i++)f[i]+=f[i-1];
        for(int i=n; i>=1; i--)w[f[(v[i]>>x)%B]]=v[i],f[(v[i]>>x)%B]--;
        for(int i=1; i<=n; i++)v[i]=w[i];
        x+=8,nr*=B;
    }
    for(int i=1; i<=n; i+=10)out<<v[i]<<" ";
    return 0;
}