Cod sursa(job #1474334)

Utilizator fluture.godlikeGafton Mihnea Alexandru fluture.godlike Data 21 august 2015 20:00:06
Problema Radix Sort Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.15 kb
#include <cstdio>

#define NMAX 10000007
#define bmask 4
#define mask (1 << bmask) - 1

using namespace std;
FILE *fin, *fout;
int n, a, b, c, v[NMAX], aux[NMAX], ct[1<<bmask];

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

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

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

    for(int i = n; i >= 1; i--)
        aux[ct[(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);
}
void citire()
{
    scanf("%d %d %d %d", &n, &a, &b, &c);
    v[1] = b;
    for(int i = 2; i<= n; ++i)
    {
        v[i] = (1LL*a*v[i-1] + b)%c;
    }
}
void afisare()
{
    for(int i = 1; i<= n; i+=10)
    {
        printf("%d ", v[i]);
    }
    printf("\n");
}

int main()
{
    fin = freopen("radixsort.in", "r", stdin);
    fout = freopen("radixsort.out", "w", stdout);
    citire();
    radixsort(v);
    afisare();
    fclose(fin);
    fclose(fout);
    return 0;
}