Cod sursa(job #1249481)

Utilizator simaghitaSima Gheorghe Eugen simaghita Data 26 octombrie 2014 23:57:11
Problema Radix Sort Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.29 kb
#include <fstream>
#include<queue>
#include<iostream>
using namespace std;

const int r=8;
const int base = ( 1<<r );
int n,A,B,C,p;
queue <int> q[2][base];
void citire()
{
    int i=1;
    ifstream fin("radixsort.in");
    fin>>n>>A>>B>>C;
    fin.close();


}
void RadixSort()
{
    int i,j;
    const int rest = base - 1;
    q[0][B & rest].push(B);
    int x, y;
    y=B;
    for (i = 2; i <= n; ++ i)
    {
        x=(1LL * A * y + 1LL * B) % C;
        q[0][x & rest].push(x);
        y=x;
    }
    int nrpasi = 32 / r + ((32 % r != 0) ? 1 : 0);
    p = 0;
    for (int pas = 1; pas < nrpasi; ++ pas, p = 1 - p)
    {
        for (j = 0; j < base; ++ j)
            while (!q[p][j].empty())
            {
                int x = q[p][j].front();
                q[p][j].pop();
                q[1 - p][(x >> (pas * r)) & rest].push(x);
            }
    }

}

void afisare()
{
    int i,nr=0;
    ofstream fout("radixsort.out");
    for(i=0;i<base;i++)
    {
        while(!q[p][i].empty())
        {
            nr++;
            if(nr%10 == 1)
                fout<<q[p][i].front()<<" ";
            q[p][i].pop();
        }
    }
    fout<<"\n";
    fout.close();
}
int main()
{
    citire();
    RadixSort();
    afisare();
    return 0;
}