Cod sursa(job #2059979)

Utilizator Teodor.mTeodor Marchitan Teodor.m Data 7 noiembrie 2017 19:39:44
Problema Radix Sort Scor 30
Compilator cpp Status done
Runda Arhiva educationala Marime 0.92 kb
#include <bits/stdc++.h>
using namespace std;

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

const int NMax = 1e7 + 5;
int v[NMax];
int temp[NMax];

void countDigit(int n, int exp)
{
	
	int count[10] = {0};

	for(int i = 1; i <= n; ++i) {
		count[(v[i] / exp) % 10]++;
	}

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

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

	for(int i = 1; i <= n; ++i) {
		v[i] = temp[i];
	}
}

int main()
{
	int n, a, b, c;

	f >> n >> a >> b >> c;

	v[1] = b;
	for(int i = 2; i <= n; ++i) {
		v[i] = (a * v[i - 1] + b) % c;
	}

	int max = v[1];

	for(int i = 2; i <= n; ++i) {
		if(v[i] > max) {
			max = v[i];
		}
	}
	

	for(int exp = 1; max/exp > 0 ; exp *= 10) {
		countDigit(n, exp);
	}

	for(int i = 1; i <= n; i += 10) {
		g << v[i] << " ";
	}

	return 0;
}