Cod sursa(job #2756114)

Utilizator lahayonTester lahayon Data 29 mai 2021 19:09:40
Problema Radix Sort Scor 30
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.84 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] = (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;
}