Cod sursa(job #2316362)

Utilizator AlexandruGabrielAliciuc Alexandru AlexandruGabriel Data 11 ianuarie 2019 17:02:49
Problema Radix Sort Scor 30
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.03 kb
#include <bits/stdc++.h>
#define N 10000005

using namespace std;

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

int a[N], b[N], n, A, B, C;

void Citire()
{
    fin >> n >> A >> B >> C;
    a[1] = B % C;
    for (int i = 1; i <= n; i++)
        a[i] = (A * a[i - 1] + B) % C;
}

void CountSort(int ex)
{
    int cnt[32] = {0};
    for (int i = 1; i <= n; i++)
        cnt[a[i] / ex % 32]++;
    for (int i = 1; i < 32; i++)
        cnt[i] += cnt[i - 1];
    for (int i = n; i >= 1; i--)
    {
        b[cnt[a[i] / ex % 32]] = a[i];
        cnt[a[i] / ex % 32]--;
    }
    for (int i = 1; i <= n; i++)
        a[i] = b[i];
}

void RadixSort()
{
    int maxi = -1;
    for (int i = 1; i <= n; i++)
        if (a[i] > maxi)
            maxi = a[i];
    for (int i = 1; maxi / i != 0; i *= 32)
        CountSort(i);
}

void Afisare()
{
    for (int i = 1; i <= n; i += 10)
        fout << a[i] << " ";
}

int main()
{
    Citire();
    RadixSort();
    Afisare();
    return 0;
}