Cod sursa(job #2439197)

Utilizator red_devil99Mancunian Red red_devil99 Data 15 iulie 2019 13:05:42
Problema Radix Sort Scor 30
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.04 kb
#include <iostream>
#include <fstream>
using namespace std;

int max(int vec[], int n){
	int max = vec[0];
	for(int i = 1; i < n; i++){
		if(vec[i] > max){
			max = vec[i];
		}
	}
	return max;
}

void countSort(int vec[], int n, int exp){
	int count[10] = {0};
	int output[n];
	for(int i = 0; i < n; i++){
		count[(vec[i]/exp)%10]++;
	}
	for(int i = 1; i < 10; i++){
		count[i] += count[i-1];
	}

	for(int i = n - 1; i >= 0; i--){
		output[count[(vec[i]/exp)%10]-1] = vec[i];
		count[(vec[i]/exp)%10]--;
	}

	for(int i = 0; i < n; i++){
		vec[i] = output[i];
	}
}

void radix(int vec[], int n){
	int maxim = max(vec, n);
	for(int exp = 1; maxim/exp > 0; exp *= 10){
		countSort(vec, n, exp);
	}
}

int main(){
	ifstream fin("radixsort.in");
	
	ofstream fout("radixsort.out");
	
    int n, vec[10000001];
    int a, b, c;
	
	fin >> n >> a >> b >> c;
	
	vec[0] = b % c;
	
    for(int i = 1; i < n; i++){
	
        vec[i] = (1LL * a * vec[i-1] % c + b) % c;
    }

	radix(vec, n);

	for(int i = 0; i < n; i += 10){
	
		fout << vec[i] <<" ";
	
	}
	fout <<'\n';

	return 0;
}