Cod sursa(job #1356339)

Utilizator retrogradLucian Bicsi retrograd Data 23 februarie 2015 13:13:08
Problema Radix Sort Scor 30
Compilator cpp Status done
Runda Arhiva educationala Marime 1.02 kb
#include<fstream>
#include<queue>
#include<cstring>

using namespace std;
typedef int var;

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

#define NO 256

var B[NO];
var V[10000002], W[10000002];
var *V1 = V, *V2 = W;
var n;

void radixsort() {
    for(var pass = 0; pass < 4; pass++) {
        memset(B, 0, sizeof(B));
        for(var i=1; i<=n; i++) {
            var val = V1[i] / (1 << (8*pass));
            val = val % (1 << 8);
            B[val]++;
        }
        for(var i=1; i<NO; i++) {
            B[i] += B[i-1];
        }
        for(var i=n; i; i--) {
            var val = V1[i] / (1 << (8*pass));
            val = val % (1 << 8);
            V2[B[val] --] = V1[i];
        }
        swap(V2, V1);
    }
}

int main() {
    var a, b, c;
    fin>>n>>a>>b>>c;
    V1[1] = b;
    for(var i=2; i<=n; i++) {
        V1[i] = (1LL*a*V[i-1] + b)%c;
    }


    radixsort();

    for(var i=1; i<=n; i+=10) {
        fout<<V1[i]<<" ";
    }


    return 0;
}