Cod sursa(job #1213512)

Utilizator batistaUPB-Oprea-Cosmin-Dumitru batista Data 28 iulie 2014 12:54:34
Problema Radix Sort Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.82 kb
#include<cstdio>
#include<algorithm>
#include<queue>/*folosesc 255 de cozi*/
#define N 10000003
using namespace std;
unsigned int n, A, B, C, v[N], k, first=255, second=65280, third=16711680, fourth=4278190080;
queue<int> Q[2][256];
void genereaza()
{
    v[1] = B;
    for(int i=2; i<=n; i++)
        v[i] = (long long)((long long)A * v[i-1] + B) % C;
}
void afiseaza()
{
    for(int i=1; i<=n; i+=10)
        printf("%d ",v[i]);
}
void radix()
{
    int i, bit=8, nr;
    k = 0;
    /*sortez dupa primul byte*/
    for(i=1; i<=n; i++)
        Q[ k ][ v[i]&first ].push(v[i]);
    /*sortez dupa al doilea byte*/
    for(i=0; i<=255; i++)
        while(!Q[k][i].empty())
        {
            nr = Q[k][i].front();
            Q[ 1-k ][ (nr&second)>>8 ].push(nr);
            Q[k][i].pop();
        }
    k=1-k;
    /*sortez dupa al treilea byte*/
    for(i=0; i<=255; i++)
        while(!Q[k][i].empty())
        {
            nr = Q[k][i].front();
            Q[ 1-k ][ (nr&third)>>16 ].push(nr);
            Q[k][i].pop();
        }
    k=1-k;
    /*sortez dupa al patrulea byte*/
    for(i=0; i<=255; i++)
        while(!Q[k][i].empty())
        {
            nr = Q[k][i].front();
            Q[ 1-k ][ (nr&fourth)>>24 ].push(nr);
            Q[k][i].pop();
        }
    k=1-k;
    nr=0;
    /*pun numerele in vector*/
    for(i=0; i<=255; i++)
        while(!Q[k][i].empty())
        {
            v[++nr] = Q[k][i].front();
            Q[k][i].pop();
        }
}
int main()
{
    /*v[1] = B
      v[i] = (A * v[i-1] + B) % C*/
    freopen("radixsort.in","r",stdin);
    freopen("radixsort.out","w",stdout);
    scanf("%d %d %d %d",&n, &A, &B, &C);
    genereaza();
    radix();
    afiseaza();

    /*std::sort(v+1, v+n+1);
    printf("\n");
    afiseaza();*/
    return 0;
}