Pagini recente » Cod sursa (job #35170) | Cod sursa (job #1838829) | Cod sursa (job #1543631) | Cod sursa (job #6652) | Cod sursa (job #2553622)
#include <bits/stdc++.h>
using namespace std;
ifstream f("radixsort.in");
ofstream g("radixsort.out");
int n,A,B,C,i,maxim,k,p,j,bucket,d[256],new_v[10000010],v[10000010];
int main()
{
f>>n>>A>>B>>C;
v[1]=B;
maxim=v[1];
for(i=2;i<=n;i++)
{
v[i]=(A*1LL*v[i-1]+B)%C;
maxim=max(maxim,v[i]);
}
/// e ca si cand as face pe ultima cifra, doar ca nu e ultima cifra sunt puteri ale lui 2 (2^8)
while(maxim)
{
k++;
maxim/=256;
}
p=0;
for(i=1;i<=k;i++) /// fac operatia de k ori
{
for(j=1;j<=n;j++)
{
/// in loc sa merg in functie de bucket-uri dupa ultima cifra, merg dupa bucket-uri in functie de configuratii de 8 biti => numarul e maxim 255 (1111 1111)
bucket=(v[j]>>p); /// adica v[j] / 2^p => impart cu q, unde q ar fi devenit mereu q=q*256
bucket=(bucket&255); /// e ca si cand fac number/p%p pentru a afla valoarea cifrei, respectiv bucket-ului pentru pozitia care ma intereseaza
/// 255 = 1111 1111
d[bucket]++;
}
/// vezi counting sort aici
for(j=1;j<=255;j++)d[j]+=d[j-1];
for(j=1;j<=n;j++)
{
/// din nou aflu bucket-ul respectiv
bucket=(v[j]>>p);
bucket=(bucket&255);
new_v[d[bucket]]=v[j];
d[bucket]--;
}
/// dam update la vectorul v
for(j=1;j<=n;j++)v[j]=new_v[j];
/// golim bucket-urile
for(j=0;j<=256;j++)d[j]=0;
}
for(i=1;i<=n;i+=10)g<<v[i]<<" ";
return 0;
}