Cod sursa(job #2897498)

Utilizator lolismekAlex Jerpelea lolismek Data 3 mai 2022 21:58:57
Problema Radix Sort Scor 30
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.84 kb
#include <iostream>
#include <fstream>
#include <vector>

#define ll long long

using namespace std;

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

const int N = 1e7, BASE = 256;
int v[N + 1];
vector <int> f[BASE + 1];

int main(){
	int n, a, b, c, maxi = -1;
	fin >> n >> a >> b >> c;

	v[1] = b;
	for(int i = 2; i <= n; i++)
		v[i] = (1ll * a * v[i - 1] + b) % c, 
		maxi = max(maxi, v[i]);

	for(ll p = BASE; p <= maxi * BASE; p *= BASE){
		for(int cif = 0; cif <= BASE; cif++)
			f[cif].clear();

		for(int i = 1; i <= n; i++){
			int cif = (v[i] % p) / (p / BASE);
			f[cif].push_back(v[i]);
		}	

		int ind = 0;
		for(int cif = 0; cif <= BASE; cif++)
			for(int i = 0; i < (int)f[cif].size(); i++)
				v[++ind] = f[cif][i];
	}

	for(int i = 1; i <= n; i += 10)
		fout << v[i] << ' ';

	return 0;
}