Cod sursa(job #2612079)

Utilizator paulvlad34Munteanu Vlad Paul paulvlad34 Data 8 mai 2020 14:30:03
Problema Radix Sort Scor 30
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.97 kb
#include<iostream>
#include<fstream>
using namespace std;

long long getMax(long long v[],long long n){
	long long mx=v[0];
	for (long long i=1;i<n;i++)
		if (v[i]>mx)
			mx=v[i];
	return mx;
	
}

void count(long long v[],long long n,long long k){
	long long output[n];
	long long i,countV[10]={0};
	
	for (i=0;i<n;i++)
		countV[(v[i]/k)%10]++;
	for (i=1;i<10;i++)
		countV[i]+=countV[i-1];
	
	for (i=n-1;i>=0;i--){
		output[countV[(v[i]/k)%10]-1]=v[i];
		countV[(v[i]/k)%10]--;
	}
	
	for (i=0;i<n;i++)
		v[i]=output[i];
	
}

void radix(long long v[],long long n){
	long long m=getMax(v,n);
	for (long long k=1;m/k>0;k*=10)
		count(v,n,k);
	
}

int main(){
	ifstream f("radixsort.in");
	ofstream f1("radixsort.out");
	long long n,a,b,c;
	f>>n>>a>>b>>c;
	long long v[n];
	for (long long i=0;i<n;i++)
		if (i==0)
			v[i]=b;
		else
			v[i]=(a*v[i-1]+b)%c;
	radix(v,n);
	
	for (long long i=0;i<n;i+=10){
		f1<<v[i]<<" ";
	}
			
	
	
}