Cod sursa(job #2070707)

Utilizator EuAlexOtaku Hikikomori EuAlex Data 19 noiembrie 2017 20:36:04
Problema Radix Sort Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.11 kb
#include <cstdio>
#include <cstring>

using namespace std;

const int bytemax = (1 << 8) - 1;

int v[10000001], myoutput[10000001];

void mysort(int n, int byte) {
    int mycount[1 + bytemax];
    memset(mycount, 0, sizeof(mycount));

    for(int i = 1; i <= n; ++ i) {
        int p = ((v[i] >> (byte * 8)) & bytemax);
        mycount[p] ++;
    }

    for(int i = 1; i <= bytemax; ++ i) {
        mycount[i] += mycount[i - 1];
    }

    for(int i = n; i >= 1; -- i) {
        int p = ((v[i] >> (byte * 8)) & bytemax);
        myoutput[mycount[p]] = v[i];
        mycount[p] --;
    }

    for(int i = 1; i <= n; ++ i) {
        v[i] = myoutput[i];
    }
}

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

    int n, a, b, c;
    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;
    }

    for(int cif = 0; cif <= 3; ++ cif) {
        mysort(n, cif);
    }

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

    return 0;
}