Cod sursa(job #1798957)

Utilizator BlackLordFMI Alex Oprea BlackLord Data 5 noiembrie 2016 16:51:50
Problema Radix Sort Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.92 kb
#include <fstream>

using namespace std;

ifstream fin ("radixsort.in");
ofstream fout ("radixsort.out");

const int N = 10000010, M = 256;

int n, A, B, C, i, v[N], a[M], w[N], p, x;
int d[4] = {0, 8, 16, 24};

int main(){
    fin >> n >> A >> B >> C;
    v[1] = B;
    for (i = 2; i <= n; ++i) {
        v[i] = (1LL * A * v[i - 1] + B) % C;
    }
    for (p = 0; p < 4; ++p) {
        for (i = 0; i < M; ++i) {
            a[i] = 0;
        }
        for (i = 1; i <= n; ++i) {
            a[((v[i] >> d[p]) & 0xff)]++;
        }
        for (i = 1; i < M; ++i) {
            a[i] += a[i - 1];
        }
        for (i = n; i > 0; --i) {
            x=((v[i] >> d[p]) & 0xff);
            w[a[x]] = v[i];
            a[x]--;
        }
        for (i = 1; i <= n; ++i) {
            v[i] = w[i];
        }
    }
    for (i = 1; i <= n; i+=10) {
        fout << v[i] << ' ';
    }
    return 0;
}