Cod sursa(job #1323026)

Utilizator MagnvsDaniel Constantin Anghel Magnvs Data 20 ianuarie 2015 16:44:55
Problema Radix Sort Scor 30
Compilator cpp Status done
Runda Arhiva educationala Marime 1.18 kb
#include <fstream>
#include <queue>

using namespace std;

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

typedef long long i64;

const int nmax = 10000000;

int v[nmax+1];

queue <int> q[2][256];

int main(  ) {
    int n, gen_a, gen_b, gen_c;
    fin >> n >> gen_a >> gen_b >> gen_c;
    v[1] = gen_b;
    q[0][v[1]&255].push(v[1]);
    for ( int i = 2; i <= n; ++ i ) {
        v[i] = ((i64)gen_a*v[i-1]+gen_b)%gen_c;
        q[0][v[i]&255].push(v[i]);
    }
    int i_aux = 0;
    for ( int i = 8; (1<<i) < gen_c; i += 8 ) {
        int ind = i/8%2, indp = (i/8+1)%2;
        for ( int j = 0; j < 256; ++ j ) {
            while ( !q[indp][j].empty() ) {
                int x = q[indp][j].front();
                q[indp][j].pop();
                q[ind][(x>>i)&255].push(x);
            }
        }
        i_aux = i/8%2;
    }


    int i_aux2 = 0;
    for ( int j = 0; j < 256; ++ j ) {
        while ( !q[i_aux][j].empty() ) {
            ++ i_aux2;
            if ( i_aux2%10 == 1 ) {
                fout << q[i_aux][j].front() << " ";
            }
            q[i_aux][j].pop();
        }
    }
    fout << "\n";

    return 0;
}