Cod sursa(job #1474366)

Utilizator Vlad_lsc2008Lungu Vlad Vlad_lsc2008 Data 21 august 2015 20:32:27
Problema Radix Sort Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.13 kb
#include <stdio.h>
#include <string.h>

#define NMAX 10000005


int v[NMAX], temp[NMAX], n;
int MASK = 255;

void vgen () {
    int a, b, c;

    scanf("%d %d %d %d", &n, &a, &b, &c);

    v[0] = b;
    for (int i = 1; i < n; ++i) {
        v[i]  = (1LL * a * v[i-1] + b) % c;
    }
}

void countsort(int *v, int *u, int x) {
    long long f[256] = {0};

    int p = 8 * x;

    for (int i = 0; i < n; ++i) {
        ++f[(v[i] >> p) & MASK];
    }

    for (int i = 1; i < 256; ++i) {
        f[i] += f[i-1];
    }

    for (int i = n-1; i >= 0; --i) {
        int pos = v[i] >> p & MASK;
        --f[pos];
        u[f[pos]] = v[i];
    }
}

void radixsort () {
    for (int i = 0; i < 4; ++i) {
        if (!(i % 2)) {
            countsort(v, temp, i);
        } else {
            countsort(temp, v, i);
        }
    }
}


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

    vgen();
    radixsort();

    for (int i = 0; i < n; i+=10) {
        printf("%d ", v[i]);
    }

    fclose(stdin);
    fclose(stdout);

    return 0;
}