Cod sursa(job #1253181)

Utilizator badea_adi1999Badea Adrian Catalin badea_adi1999 Data 31 octombrie 2014 21:20:26
Problema Radix Sort Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.82 kb
#include <cstdio>
#include <algorithm>
#include <list>
#define BASE 10
using namespace std;
FILE *f=fopen("radixsort.in","r");
FILE *g=fopen("radixsort.out","w");
int n,a,b,c,put=1,maxim,nr;
bool ok;
int v[10000005];
list <int> bucket[BASE];

void radix(int put)
{int i,k;
list <int>::iterator it;
for (i=1;i<=n;i++) bucket[(v[i]/put)%10].push_back(v[i]);
i=0;k=0;
for (i=0;i<BASE;i++)
			{for (it= bucket[i].begin();it!=bucket[i].end();v[k++]=*(it++));
             bucket[i].clear();}
}

int main()
{int i,j;
long long ll;
fscanf(f,"%d %d %d %d",&n,&a,&b,&c);
v[1]=b;
for (i=2;i<=n;i++) {ll=1LL*(1LL*a*(v[i-1])+b)%c;
                    v[i]=ll;
                    maxim=max(maxim,v[i]);}


while (1LL*put<=maxim)
{radix(put);
put=put*10;}


for (i=1;i<=n;i+=10) fprintf(g,"%d ",v[i]);
return 0;
}