Cod sursa(job #2651822)

Utilizator BogdanTicuTicu Bogdan Valeriu BogdanTicu Data 23 septembrie 2020 17:37:12
Problema Radix Sort Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.77 kb
#include <bits/stdc++.h>

using namespace std;

ifstream in("radixsort.in");
ofstream out("radixsort.out");

int v[10000001];
int aux[10000001];
int cnt[260],indexx[260];
int radixsort(int v[],int aux[],int n,int current)
{
	memset(cnt,0,sizeof(cnt));
	for(int i=0;i<n;i++)
	{
		int cifra=((v[i]>>current) & 255);
		++cnt[cifra];
	}
	indexx[0]=0;
	for(int i=1;i<256;i++)
		indexx[i]=cnt[i-1]+indexx[i-1];
	for(int i=0;i<n;i++)
	{
		int cifra=((v[i]>>current) & 255);
		aux[indexx[cifra]++]=v[i];	
	}
}
int main()
{
	long long n,a,b,c,biti=sizeof(v[0]);
	in>>n>>a>>b>>c;
	v[0]=b;
	for(int i=1;i<n;i++)
		v[i]=(a*v[i-1]%c+b)%c;
	for(int i=0;i<biti;i++)
	{
		if(i%2) radixsort(aux,v,n,i*8);
		else radixsort(v,aux,n,i*8);
	}
	for(int i=0;i<n;i+=10)
		out<<v[i]<<" ";
	out<<"\n";
	return 0;
}