Cod sursa(job #1354448)

Utilizator AndreyPAndrei Poenaru AndreyP Data 21 februarie 2015 20:26:03
Problema Radix Sort Scor 30
Compilator cpp Status done
Runda Arhiva educationala Marime 1.06 kb
#include <cstdio>

#define N_MAX 10000010

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

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 void solve() {
    int next = 0, prev = 1;

    for (int i = 0; i < 31; ++i) {
        int mask = (1 << i);
        next ^= 1;
        prev ^= 1;
        int i1 = 0, i2 = 0;

        for (int j = 0; j < N; ++j) {
            if (!(v[prev][j] & mask)) {
                ++i2;
            }
        }

        for (int j = 0; j < N; ++j) {
            if (v[prev][j] & mask) {
                v[next][i2++] = v[prev][j];
            } else {
                v[next][i1++] = v[prev][j];
            }
        }
    }
}

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

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

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

    return 0;
}