Cod sursa(job #1470439)

Utilizator tudi98Cozma Tudor tudi98 Data 11 august 2015 02:46:07
Problema Radix Sort Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.96 kb
#include <fstream>
using namespace std;

const int Nmax = 10000001;
const int bmask = 4;
const int mask = (1 << bmask) - 1;

int N,A,B,C;
int v[Nmax];
int aux[Nmax];
int c[1 << bmask];

void countsort(int a[], int p)
{
    for(int i = 0; i <= mask; i++)
        c[i] = 0;

    for(int i = 1; i <= N; i++)
        ++c[(a[i] & (mask << p)) >> p];

    for(int i = 1; i <= mask; i++)
        c[i] += c[i-1];

    for(int i = N; i >= 1; i--)
        aux[c[(a[i] & (mask << p)) >> p]--] = a[i];

    for(int i = 1; i <= N; i++)
        a[i] = aux[i];
}

void radixsort(int a[])
{
    for(int i = 0; i < 32; i += bmask)
        countsort(a,i);
}

int main()
{
    ifstream fin("radixsort.in");
    ofstream fout("radixsort.out");

    fin >> N >> A >> B >> C;

    v[1] = B;
    for(int i = 2; i <= N; i++)
        v[i] = (1LL * A * v[i-1] + B) % C;

    radixsort(v);

    for(int i = 1; i <= N; i += 10)
        fout << v[i] << " ";
}