Pagini recente » Cod sursa (job #1583588) | Cod sursa (job #240517) | Cod sursa (job #1788425) | Cod sursa (job #226128) | Cod sursa (job #2527875)
#include <iostream>
#include <cstdio>
using namespace std;
const int nmax = 10000000;
int v[nmax+1],new_v[nmax+1];
void copy_new_v(int n){
for(int i=1; i<=n; i++)
v[i] = new_v[i];
}
int power(int digit){
int ans = 1;
while(digit--)
ans *= 10;
return ans;
}
void counting_sort(int digit, int n){
int cif[10];
int p10 = power(digit);
int i;
for(i=0; i<10; i++)
cif[i] = 0;
for(i=1; i<=n; i++)
cif[v[i]/p10%10]++;
for(i=1; i<10; i++)
cif[i] += cif[i-1];
for(i=9; i>0; i--)
cif[i] = cif[i-1];
cif[0] = 0;
for(i=1; i<=n; i++)
new_v[++cif[v[i]/p10%10]] = v[i];
copy_new_v(n);
}
int main()
{
FILE *fin, *fout;
int n,a,b,c,i,maxim,cif;
fin = fopen("radixsort.in","r");
fout = fopen("radixsort.out","w");
fscanf(fin,"%d %d %d %d",&n,&a,&b,&c);
v[1] = maxim = b;
for(i=2; i<=n; i++){
v[i] = (1LL*a*v[i-1] + 1LL*b)%c;
maxim = maxim > v[i] ? maxim : v[i];
}
cif = 0;
while(maxim){
cif++;
maxim /= 10;
}
for(i=0; i<cif; i++)
counting_sort(i, n);
for(i=1; i<=n; i+=10)
fprintf(fout,"%d ",v[i]);
fclose(fin);
fclose(fout);
return 0;
}