Cod sursa(job #2619517)

Utilizator AlexVulpoiuAlexandru Vulpoiu AlexVulpoiu Data 27 mai 2020 20:51:59
Problema Radix Sort Scor 30
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.34 kb
#include <fstream>
#include <algorithm>

using namespace std;

int aux[10000005], aux2[10000005], v[10000005];

void countsort(int w[], const int& m, const int& p, const int& k)
{
    int i, fr[260] = {0};

    for(i = 0; i < m; i++)
        fr[(w[i] >> k) & 255]++;
    for(i = 1; i < 256; i++)
        fr[i] += fr[i - 1];
    for(i = m - 1; i >= 0; i--)
        if(p == 1 || p ==  256 * 256)
        {
            aux[fr[(w[i]  >> k) & 255] - 1] = w[i];
            fr[(w[i] >> k) & 255]--;
        }
        else
        {
            aux2[fr[(w[i] >> k) & 255] - 1] = w[i];
            fr[(w[i] >> k) & 255]--;
        }
}

void radixsort(int w[], const int& m)
{
    int i, max1;

    max1 = w[0];
    for(i = 1; i < m; i++)
        max1 = max(max1, w[i]);
    countsort(w, m, 1, 0);
    countsort(aux, m, 256, 8);
    countsort(aux2, m, 256 * 256, 16);
    countsort(aux, m, 256 * 256 * 256, 24);
}

int main()
{
    ifstream f("radixsort.in");
    ofstream g("radixsort.out");

    int n, a, b, c, i;

    f >> n >> a >> b >> c;
    f.close();

    v[0] = b;
    for(i = 1; i < n; i++)
        v[i] = (int)(((1LL * a * (1LL * v[i - 1])) % (1LL * c) + 1LL * b) % (1LL * c));

    radixsort(v, n);

    for(i = 0; i < n; i += 10)
        g << aux2[i] << ' ';
    g << '\n';
    g.close();

    return 0;
}