Pagini recente » Cod sursa (job #3120813) | Cod sursa (job #3195921) | Cod sursa (job #1984386) | Cod sursa (job #2859362) | Cod sursa (job #2911121)
#include <bits/stdc++.h>
using namespace std;
ifstream f("radixsort.in");
ofstream g("radixsort.out");
const int N = 10000001;
int n,poz[256];
unsigned a,b,c,V[N],W[N],*v,*w;
inline unsigned func(unsigned x)
{
x=1LL*a*x%c;
x=(x+b)%c;
return x;
}
inline unsigned rot(unsigned x)
{
unsigned pref = x>>8;
unsigned suff = x&255;
unsigned ret = (suff<<24)|pref;
return ret;
}
int main()
{
f>>n>>a>>b>>c;
int x=b,k=0;
v=V;w=W;
/// se generaza sirul initial
for(int i=1;i<=n;i++)
{
v[++k]=x;
x=func(x);
}
for(int t=0;t<4;t++)/// de 4 ori
{
/// se costruieste sirul contoarelor pentru cele 256 prefixe
for(int i=1;i<=n;i++)
poz[v[i]&255]++;
/// se realizeaza sirul sumelor partiale pentru contoare
for(int i=1;i<256;i++)
poz[i]+=poz[i-1];
/// se aseaza pe w sirul pe cele 255 buchete
for(int i=n;i>=1;i--)
{
int buchet=v[i]&255;
w[poz[buchet]]=rot(v[i]);
poz[buchet]--;
/// pe noul sir valoare se pune cu ultimul octet deja mutat in fata
}
swap(v,w);
/// se resetaza contoarele la 0 pentru urmatoarea parcurgere
for(int i=0;i<256;i++)
poz[i]=0;
}
for(int i=1;i<=n;i+=10)
g<<v[i]<<' ';
return 0;
}