Cod sursa(job #1145941)

Utilizator eugen_ptrEugen Patru eugen_ptr Data 18 martie 2014 16:13:26
Problema Radix Sort Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.78 kb
#include <iostream>
#include <cstdio>
#include <vector>

#define Nmax 10000005

using namespace std;


int n, a, b, c;
int v[Nmax];

void citire()
{
    scanf("%d %d %d %d",&n, &a, &b, &c);
    v[1] = b;
    for (int i=2; i<=n; i++)
        v[i] = (a * v[i-1] + b) % c;
}

void radix(int nr)
{
    vector<int> L[300];
    for (int i=1; i<=n; i++)
        L[(v[i]>>nr) & 255].push_back(v[i]);

    n = 0;
    for (int i=0; i<=255; i++)
    {
        for (int j=0; j<L[i].size(); j++)
            v[++n] = L[i][j];
    }
}

int main()
{
    freopen("radixsort.in","r",stdin);
    freopen("radixsort.out","w",stdout);
    citire();
    for (int i=0; i<=32; i+=8)
        radix(i);
    for (int i=1; i<=n; i+=10)
        printf("%d ",v[i]);
    return 0;
}