Cod sursa(job #3176064)

Utilizator andreic06Andrei Calota andreic06 Data 26 noiembrie 2023 18:02:45
Problema Radix Sort Scor 30
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.32 kb
#include <bits/stdc++.h>

using namespace std;
using int64 = long long;

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

const int N_MAX = 1e7;
const int DIGIT = 10;


int n;
int64 currInput[N_MAX];
int freq[DIGIT], pos[DIGIT];
int64 newInput[N_MAX];

void radixStep (int power) {
   for (int d = 0; d < DIGIT; d ++)
      freq[d] = 0;

   for (int i = 0; i < n; i ++)
      freq[currInput[i] / power % 10] ++;

   pos[0] = 0;
   for (int d = 1; d < DIGIT; d ++)
      pos[d] = pos[d - 1] + freq[d - 1];

   for (int i = 0; i < n; i ++) {
      newInput[pos[currInput[i] / power % 10]] = currInput[i];
      pos[currInput[i] / power % 10] ++;
   }

   for (int i = 0; i < n; i ++)
      currInput[i] = newInput[i];
}

void radixSort (void) {
    int64 maxValue = 0;
    for (int i = 0; i < n; i ++)
       maxValue = max (maxValue, currInput[i]);

    for (int power = 1; power <= maxValue; power *= 10)
       radixStep (power);
}
int main()
{
   /**in >> n;
   for (int i = 0; i < n; i ++)
      in >> currInput[i];**/

   int64 a, b, c; in >> n >> a >> b >> c;
   currInput[0] = b;
   for (int i = 1; i < n; i ++)
      currInput[i] = (currInput[i - 1] * a + b) % c;

   radixSort ();
   for (int i = 0; i < n; i += 10)
      out << currInput[i] << " ";
    return 0;
}