Cod sursa(job #1315765)

Utilizator simaghitaSima Gheorghe Eugen simaghita Data 13 ianuarie 2015 03:08:16
Problema Radix Sort Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.21 kb
#include <iostream>
#include <fstream>
#include<queue>
#define rest 8
#define base (1<<rest)
using namespace std;
int n,A,B,C,r;
queue <int> q[2][base];
void Push()
{
    r=base-1;
    q[0][B & r].push(B);
    int a,b;
    b=B;
    for(int i=2;i<=n;++i)
    {
        a=(1LL * A * b + 1LL*B)%C;
        q[0][a & r].push(a);
        b=a;
    }
}
void citire()
{
    ifstream fin("radixsort.in");
    fin>>n>>A>>B>>C;
    fin.close();
    Push();
}
void radixSort()
{
    int ind=0,i,j,elem;
    int steps=32/rest;
    for(i=1;i<steps;++i)
    {
        for(j=0;j<base;++j)
        {
            while(!q[ind][j].empty())
            {
                elem=q[ind][j].front();
                q[ind][j].pop();
                q[1-ind][(elem>>(i*rest)) & r].push(elem);

            }
        }
        ind=1-ind;
    }

    ofstream fout("radixsort.out");
    j=0;
    for(i=0;i<base;++i)
    {
        while(!q[ind][i].empty())
        {
            ++j;
            if(j%10==1)
                fout<<q[ind][i].front()<<" ";
            q[ind][i].pop();
        }
    }
    fout<<"\n";
    fout.close();
}

int main()
{
    citire();
    radixSort();
    return 0;
}