Cod sursa(job #2975223)

Utilizator vladburacBurac Vlad vladburac Data 5 februarie 2023 21:28:14
Problema Radix Sort Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.82 kb
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1e7;

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

int v[MAXN], aux[MAXN];
int cnt[10];
int n;

void radixSort() {
  int i, put;
  for( put = 1; put <= 1e9; put*=10 ) {
    for( i = 0; i < 10; i++ )
      cnt[i] = 0;
    for( i = 0; i < n; i++ )
      cnt[v[i]/put%10]++;
    for( i = 1; i < 10; i++ )
      cnt[i] += cnt[i-1];
    for( i = n - 1; i >= 0; i-- ) {
      aux[cnt[v[i]/put%10]-1] = v[i];
      cnt[v[i]/put%10]--;
    }
    for( i = 0; i < n; i++ )
      v[i] = aux[i];
  }
}
int main() {
  int a, b, c, i;
  fin >> n >> a >> b >> c;
  v[0] = b;
  for( i = 1; i < n; i++ ) {
    v[i] = ( 1LL * a * v[i-1] + b ) % c;
  }
  radixSort();
  for( i = 0; i < n; i += 10 )
    fout << v[i] << " ";
  return 0;
}