Cod sursa(job #1494469)

Utilizator LurchssLaurentiu Duma Lurchss Data 1 octombrie 2015 10:13:50
Problema Radix Sort Scor 30
Compilator cpp Status done
Runda Arhiva educationala Marime 1.01 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <math.h>

#define max 10000002
using namespace std;
int n,A,B,C;
vector<int> v;
vector<int> q[10];
int lmax;
void read()
{
    scanf("%d %d %d %d",&n,&A,&B,&C);
    v.push_back(B);
    for(int i=1;i<n;i++)
        v.push_back((A*v[i-1] + B ) % C);
    while(C) lmax++,C/=10;
}

int power(int x,int p)
{
    int aux=1;
    for(int i=1;i<=p;i++)
        aux*=x;
    return aux;
}
void rad_sort()
{
    int p=0;
    for(int i=1;i<=lmax;i++)
        {for(int j=0;j<n;j++)
            q[(v[j]/power(10,p))%10].push_back(v[j]);
        v.clear();
        for(int i=0;i<=9;i++)
            for(int j=0;j<q[i].size();j++)
                v.push_back(q[i][j]);
        for(int i=0;i<=9;i++)
            q[i].clear();
        p++;}
    for(int i=0;i<n;i+=10)
        printf("%d ",v[i]);
}
int main()
{
    freopen("radixsort.in","r",stdin);
    freopen("radixsort.out","w",stdout);
    read();
    rad_sort();
    return 0;
}