Cod sursa(job #1675511)

Utilizator tudormaximTudor Maxim tudormaxim Data 5 aprilie 2016 12:50:50
Problema Radix Sort Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.84 kb
#include <iostream>
#include <fstream>
#include <algorithm>
using namespace std;

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

const int nmax = 1e7+5;
int v[nmax], w[nmax], fr[18], n, a, b, c;

void RadixSort() {
    int i, j;
    for(i=0; i<31; i+=4) {
        fill(fr, fr+18, 0);
        for(j=1; j<=n; j++)
            fr[(v[j]>>i)&15]++;
        for(j=1; j<=16; j++)
            fr[j]+=fr[j-1];
        for(j=n; j; j--)
            w[fr[(v[j]>>i)&15]--]=v[j];
        for(j=n; j; j--)
            v[j]=w[j];
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    int i;
    fin >> n >> a >> b >> c;
    v[1]=b;
    for(i=2; i<=n; i++)
        v[i]=(1LL*a*v[i-1]+b)%c;
    RadixSort();
    for(i=1; i<=n; i+=10)
        fout << v[i] << " ";
    fin.close();
    fout.close();
    return 0;
}