Cod sursa(job #2707411)

Utilizator UnknownPercentageBuca Mihnea-Vicentiu UnknownPercentage Data 16 februarie 2021 22:21:12
Problema Radix Sort Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.83 kb
#include <bits/stdc++.h>

using namespace std;

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

int a[10000001];
int N, A, B, C, mx;

void countSort(int Exp){
	int output[N + 1];
	int i, count[10] = {};
	
	for(int i = 1;i <= N;i++)
		count[(a[i] / Exp) % 10]++;

	for(int i = 1;i < 10;i++)
		count[i] += count[i - 1];

	for(int i = N;i >= 1;i--){
		output[count[(a[i] / Exp) % 10] - 1] = a[i];
		count[(a[i] / Exp) % 10]--;
	}

	for (i = 1; i <= N; i++) 
        a[i] = output[i]; 

}

void radixsort(){

	for(int Exp = 1;mx / Exp > 0;Exp *= 10)
		countSort(Exp);
}


int main(){

	f >> N >> A >> B >> C;
	a[1] = B % C, mx = a[1];
	for(int i = 2;i <= N;i++){
		a[i] = (1LL * A * a[i - 1] + B) % C;
		mx = max(mx, a[i]);
	}

	radixsort();

	for(int i = 1;i <= N;i += 10)
		g << a[i] << " ";
}