Cod sursa(job #1354465)

Utilizator AndreyPAndrei Poenaru AndreyP Data 21 februarie 2015 20:35:50
Problema Radix Sort Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.11 kb
#include <cstdio>
#include <cstring>

#define N_MAX 10000010

int N, A, B, C;
int v[2][N_MAX];
int cnt[257];

inline void read() {
    scanf("%d%d%d%d", &N, &A, &B, &C);

    v[0][0] = B;
    for (int i = 1; i < N; ++i) {
        v[0][i] = ((long long)A * v[0][i - 1] + B) % C;
    }
}

inline int getByte(int x, int b) {
    return ((x >> (8 * b)) & 0xFF);
}

inline void solve() {
    int next = 0, prev = 1;

    for (int i = 0; i < 4; ++i) {
        next ^= 1;
        prev ^= 1;

        memset(cnt, 0, sizeof(cnt));
        for (int j = 0; j < N; ++j) {
            ++cnt[getByte(v[prev][j], i) + 1];
        }

        for (int j = 1; j < 256; ++j) {
            cnt[j] += cnt[j - 1];
        }

        for (int j = 0; j < N; ++j) {
            v[next][cnt[getByte(v[prev][j], i)]++] = v[prev][j];
        }
    }
}

inline void print() {
    printf("%d", v[0][0]);
    for (int i = 10; i < N; i += 10) {
        printf(" %d", v[0][i]);
    }
    fputc('\n', stdout);
}

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

    read();
    solve();
    print();

    return 0;
}