Cod sursa(job #1105869)

Utilizator proflaurianPanaete Adrian proflaurian Data 12 februarie 2014 10:40:02
Problema Radix Sort Scor 30
Compilator cpp Status done
Runda Arhiva educationala Marime 1.05 kb
#include <cstdio>
#include <vector>
#define N 10000010
using namespace std;
unsigned a,b,c,k,x,y;
int i,j,n;
vector<unsigned> B[2][256],V;
int main()
{
    freopen("radixsort.in","r",stdin);
    freopen("radixsort.out","w",stdout);
    scanf("%d%d%d%d",&n,&a,&b,&c);
    x=b;k=x&255;y=(x>>8)|(k<<24);B[0][k].push_back(y);
    b%=c;a%=c;
    for(i=1;i<n;i++)
    {
        x=(1LL*a*x%c+b)%c;
        k=x&255;y=(x>>8)|(k<<24);B[0][k].push_back(y);
    }
    a=0;c=1;
    for(int cnt=3;cnt;cnt--)
    {
        for(i=0;i<=255;i++)
        if(B[a][i].size())
        {
            for(vector<unsigned>::iterator it=B[a][i].begin();it!=B[a][i].end();it++)
            {
                x=*it;
                k=x&255;x=(x>>8)|(k<<24);B[c][k].push_back(x);
            }
            B[a][i].resize(0);
        }
        a=1-a;c=1-c;
    }
    for(i=0;i<=255;i++)
        for(vector<unsigned>::iterator it=B[a][i].begin();it!=B[a][i].end();it++)
            V.push_back(*it);
    for(i=0;i<n;i+=10)
        printf("%d ",V[i]);
    return 0;
}