Cod sursa(job #2901415)

Utilizator mariailincailinca maria nechita mariailinca Data 13 mai 2022 17:57:47
Problema Radix Sort Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.03 kb
#include <fstream>

using namespace std;

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

const int MAXI=10000001;
int a[MAXI];

void countsort(int a[], int n, int exp)
{
  int res[n], i, cnt[10] = {0};

  for (int i =1; i <=n; i++)
    cnt[(a[i] / exp) % 10]++;

  for (int j =1; j<10; j++)
    cnt[j] += cnt[j-1];


  for (int i =n; i>=1; i--)
  {
    res[cnt[(a[i] / exp) % 10] - 1] = a[i];
    cnt[(a[i] / exp) % 10]--;
  }

  for (i =1; i<=n; i++)
    a[i]=res[i];
}

void radixsort(int a[], int n)
{
  int p;
  int maxi = a[1];
  for (int i=2; i<=n; i++)
    if (a[i] > maxi)
      maxi = a[i];
  for (p = 1; maxi/p > 0; p *= 10)
    countsort(a, n, p);
}


int main()
{
    int N,A,B,C;
    fin >> N >> A >> B >> C;
    for (int i=1;i<=N;i++)
        {
            if (i==1)
                a[i]=B;
            else
                a[i]=(1ll*A * a[i-1] + B) % C;
        }
    radixsort(a,N);
    for (int i=1;i<=N;i+=10)
        fout << a[i] << " ";
    return 0;
}