Cod sursa(job #1323102)

Utilizator MagnvsDaniel Constantin Anghel Magnvs Data 20 ianuarie 2015 17:35:40
Problema Radix Sort Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1 kb
#include <cstring>
#include <fstream>

using namespace std;

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

typedef long long i64;

const int nmax = 10000000;

int v[nmax+1], v2[nmax+1];
int f[256];

int main(  ) {

    int n, gen_a, gen_b, gen_c;
    fin >> n >> gen_a >> gen_b >> gen_c;
    v[1] = gen_b;
    for ( int i = 2; i <= n; ++ i ) {
        v[i] = ((i64)gen_a*v[i-1]+gen_b)%gen_c;
    }
    for ( int i = 0; i < 31; i += 8 ) {
        for ( int k = 1; k < 256; ++ k ) {
            f[k] = 0;
        }
        for ( int j = 1; j <= n; ++ j ) {
            ++f[(v[j]>>i)&255];
        }
        for ( int k = 1; k < 256; ++ k ) {
            f[k] += f[k-1];
        }

        for ( int j = n; j >= 1; -- j ) {
            v2[f[(v[j]>>i)&255]] = v[j];
            --f[(v[j]>>i)&255];
        }
        memcpy( v, v2, sizeof(v));
    }

    for ( int i = 1; i <= n; i += 10 ) {
        fout << v[i] << " ";
    }
    fout << "\n";

    return 0;
}