Cod sursa(job #1796041)

Utilizator emanuel_rRamneantu Emanuel emanuel_r Data 3 noiembrie 2016 01:22:14
Problema Radix Sort Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.98 kb
#include<iostream>
#include<fstream>

using namespace std;

ifstream f("radixsort.in");
ofstream g("radixsort.out");

int const NMax = 10000005;
int A[NMax], B[NMax], car[35];
int n, a, b, c;

void Read()
{
    f>>n>>a>>b>>c;
    A[1] = b;
    for(int i=2; i<=n; i++)
        A[i] = (1LL * a * A[i-1] + b) % c;
}

void Solve()
{
    int p = 0, i, num;
    while(p < 32){
        for(i=1; i<=n; i++){
            num = (A[i]>>p) & 31;
            car[num]++;
        }
        for(i=1; i<=31; i++)
            car[i] += car[i-1];

        for(i=n; i>0; i--){
            num = (A[i]>>p) & 31;
            B[car[num]] = A[i];
            car[num]--;
        }

        for(i=1; i<=n; i++)
            A[i] = B[i];

        for(i=0; i<=32; i++)
            car[i] = 0;

        p += 5;
    }
}

void Print()
{
    for(int i=1; i<=n; i+=10)
        g<<A[i]<<" ";
    g<<"\n";
}

int main()
{
    Read();
    Solve();
    Print();
    return 0;
}