Cod sursa(job #2609391)

Utilizator AlexNicuNicu Alexandru AlexNicu Data 2 mai 2020 16:02:10
Problema Radix Sort Scor 30
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.77 kb
#include <fstream>

using namespace std;
int v[10000005], poz[10000005], aux[10000005], nr[10];
ifstream cin ( "radixsort.in" );
ofstream cout ( "radixsort.out" );
int main() {
  int n, a, b, c, i, p, k, j;
  cin >> n >> a >> b >> c;
  v[0] = b;
  for( i = 1; i < n; i++ ) {
    v[i] = ( 1LL * a * v[i - 1] + b ) % c;
  }
  p = 1;
  for( k = 0; k < 11; k++ ) {
    for ( i = 0; i < 10; i++ )
      nr[i] = 0;
    for ( j = 0; j < n; j++ )
      nr[v[j] / p % 10]++;
    poz[0] = 0;
    for ( i = 1; i < 10; i++ )
      poz[i] = poz[i - 1] + nr[i - 1];
    for ( j = 0; j < n; j++ )
      aux[poz[v[j] / p % 10]++] = v[j];
    for ( j = 0; j < n; j++ )
      v[j] = aux[j];
    p *= 10;
  }
  for ( i = 0; i < n; i += 10 )
    cout << v[i] << " ";
  return 0;
}