Cod sursa(job #2756117)

Utilizator lahayonTester lahayon Data 29 mai 2021 19:17:08
Problema Radix Sort Scor 30
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.98 kb
	
#include <fstream>
	
#include <vector>
	
#include <algorithm>
	
 
	
using namespace std;
	
 
	
int main()
	
{ 
	
 
	
   ifstream cin("radixsort.in");
	
   ofstream cout("radixsort.out");
	
 
	
   int N, A, B, C;
	
   cin >> N >> A >> B >> C;
	
 
	
   vector<int> V(N);
	
   V[0] = B;
	
   int maxvalue = B;
	
   for(int i = 1; i < N; ++i){
	
        V[i] = ((long long)A * V[i - 1] + B) % C;
	
        maxvalue = max(maxvalue, V[i]);
	
   }
	
   
	
   
	
   long long expo = 1;
	
   while(maxvalue >= expo){
	
 
	
       vector<int> buckets[10];
	
       for(int i = 0; i < N; ++i)
	
            buckets[V[i] / expo % 10].push_back(V[i]);
	
 
	
        for(int i = 0, j = 0; i < 10; ++i){
	
            for(int h = 0; h < buckets[i].size(); ++h)
	
                V[j++] = buckets[i][h];
	
        }
	
       expo *= 10;
	
   }
	
 
	
   for(int i = 0; i < N; i += 10)
	
    cout << V[i] << " ";
	
 
	
  return 0;
	
}