Cod sursa(job #1766155)

Utilizator dodecagondode cagon dodecagon Data 27 septembrie 2016 17:11:45
Problema Radix Sort Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.74 kb
#include <stdio.h>
#include <string.h>


int cnt[259],ind[259],init[10000009],temp[10000009],n,i,a,b,c;


inline void sort(int * a, int * b,int x)
{

	memset(cnt,0,sizeof(cnt));

	for (i=0;i<n;++i)
		cnt[(a[i]>>x) & 255]++;
     ind[0]=0;
	for (i=1;i<256;++i)
		ind[i]=ind[i-1]+cnt[i-1];

	for (i=0;i<n;++i)
		b[ind[(a[i]>>x) & 255]++]=a[i];

}

int main(int argc, char const *argv[])
{
  
   freopen("radixsort.in","r",stdin);
   freopen("radixsort.out","w",stdout);

	scanf("%d%d%d%d",&n,&a,&b,&c);

    init[0]=b%c;
	for (i=1;i<n;++i)
		init[i]=(1LL*init[i-1]*a%c+b)%c;


	sort(init,temp,0);
	sort(temp,init,8);
	sort(init,temp,16);
	sort(temp,init,24);


	for (i=0;i<n;i+=10)
		printf("%d ",init[i]);

   
   fclose(stdin);
   fclose(stdout);
	
	return 0;
}