Cod sursa(job #1222885)

Utilizator rangerChihai Mihai ranger Data 24 august 2014 17:43:38
Problema Radix Sort Scor 30
Compilator cpp Status done
Runda Arhiva educationala Marime 0.75 kb
#include<fstream>
#include<vector>
using namespace std;
#define base 10
#define nmax 10000000

ifstream cin("radixsort.in");
ofstream cout("radixsort.out");

int n,A,B,C,arr[nmax];
vector<int> bucket[base];

int main()
{
    cin>>n>>A>>B>>C;
    arr[1]=B;
    int m=-1,i;
    for (i=2;i<=n;i++) {
        arr[i]=(A*arr[i-1]+B)%C;
        m=(arr[i]>m) ? arr[i] : m;
    }
    for (int exp=1; exp<=m; exp*=base) {
        for (i=1;i<=n;i++)
            bucket[(arr[i]/exp)%base].push_back(arr[i]);
        int k=0;
        for(i=0;i<base;i++) {
            for (int j=0;j<bucket[i].size();++j)
                arr[++k]=bucket[i][j];
            bucket[i].clear();
        }
    }
    for (i=1;i<=n;i+=10) cout<<arr[i]<<" ";
    return 0;
}