Cod sursa(job #1494252)

Utilizator vladdy47Bucur Vlad Andrei vladdy47 Data 30 septembrie 2015 21:12:29
Problema Radix Sort Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1 kb
# include <cstdio>
# include <cstring>
# define MAX (10000000 + 10)

using namespace std;

int n, i, A, B, C;
int v[MAX], aux[MAX], ap[1 << 8];


void radixs (int p)
{   int i;
    int mask = (1 << 8) - 1;

    memset(ap, 0, sizeof(ap));

    for (i = 1; i <= n; i++)
        ap[( v[i] & (mask << p) ) >> p]++;

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

    for (i = mask; i >= 1; i--)
        ap[i] = ap[i-1];

    ap[0] = 0;

    for (i = 1; i <= n; i++)
        aux[++ap[( v[i] & (mask << p) ) >> p]] = v[i];

   for (i = 1; i <= n; i++)
        v[i] = aux[i];

}

int main ()

{
    freopen("radixsort.in","r",stdin);
    freopen("radixsort.out","w",stdout);

    scanf("%d %d %d %d\n", &n, &A, &B, &C);

    v[1] = B;

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

    for (i = 0; i < 32; i += 8)
        radixs(i);

    for (i = 1; i <= n; i += 10)
        printf("%d ", v[i]);

    printf("\n");
    return 0;
}