Pagini recente » Cod sursa (job #1422133) | Cod sursa (job #2905887) | Cod sursa (job #808922) | Cod sursa (job #622935) | Cod sursa (job #2540625)
#include <fstream>
#define dim 10000010
using namespace std;
int a[2][dim];
int f[270];
int i,n,p,k,A,B,C,P;
inline int OctetulP (int x) {
return ((x >> P)&255);
}
void stergere() {
for (int i=0;i<=256;i++) {
f[i]=0;
}
}
void sumaPartiala() {
for (int i=1;i<=255;i++) {
f[i]+=f[i-1];
}
}
void sortare (int a[],int b[]) {
int x;
for (int i=1;i<=n;i++) {
f[OctetulP(a[i])]++;
}
sumaPartiala();
for (int i=n;i>=1;i--) {
b[f[x = OctetulP(a[i])]]=a[i];
f[x]--;
}
}
int main() {
ifstream fin("radixsort.in");
ofstream fout("radixsort.out");
fin>>n>>A>>B>>C; ///nr&255=valoarea reprezentata de ultimul octet al numarului
a[k][1]=B; ///nr>>p*8=numarul fara ultimul octet
for (i=2;i<=n;i++) {
///a[k][i]=((1LL*(A%C)*1LL*(a[k][i-1])%C)%C+1LL*B)%C;
a[k][i] = (A * 1LL * a[k][i-1] + B) % C;
}
// fout<<19514%256<<"\n";
// fout<<19514/256;
k=0;
P = 0;
for (p=0;p<4;p++) {
sortare(a[k],a[1-k]);
stergere();
P += 8;
k=1-k;
}
for(i=1;i<=n;i+=10) {
fout<<a[k][i]<<" ";
}
return 0;
}