Cod sursa(job #1117224)

Utilizator BlackLordFMI Alex Oprea BlackLord Data 23 februarie 2014 11:59:05
Problema Radix Sort Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.78 kb
#include <fstream>
#define DIM 10000010
using namespace std;
ifstream f("radixsort.in");
ofstream g("radixsort.out");
int n, A, B, C, i, v[DIM], a[256], w[DIM], p, x;
int d[4]={0, 8, 16, 24};
int main(){
    f>>n>>A>>B>>C;
    v[1]=B;
    for(i=2; i<=n; i++)
        v[i]=(int)((1LL*A*v[i-1]+B)%C);
    for(p=0; p<4; p++)
    {
        for(i=0; i<256; i++)
            a[i]=0;
        for(i=1; i<=n; i++)
            a[ ( (v[i]>>d[p])&0xff ) ]++;
        for(i=1; i<256; i++)
            a[i]+=a[i-1];
        for(i=n; i>0; i--)
        {
            x=( (v[i]>>d[p])&0xff );
            w[ a[x] ]=v[i];
            a[x]--;
        }
        for(i=1; i<=n; i++)
            v[i]=w[i];
    }
    for(i=1; i<=n; i+=10)
        g<<v[i]<<' ';
    g<<"\n";
    return 0;
}