Cod sursa(job #2619494)

Utilizator AlexVulpoiuAlexandru Vulpoiu AlexVulpoiu Data 27 mai 2020 20:09:04
Problema Radix Sort Scor 30
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.23 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)
{
    int i, fr[65540] = {0};

    for(i = 0; i < m; i++)
        fr[(w[i] / p) & 65535]++;
    for(i = 1; i < 65536; i++)
        fr[i] += fr[i - 1];
    for(i = m - 1; i >= 0; i--)
        if(p == 1)
        {
            aux[fr[(w[i] / p) & 65535] - 1] = w[i];
            fr[(w[i] / p) & 65535]--;
        }
        else
        {
            aux2[fr[(w[i] / p) & 65535] - 1] = w[i];
            fr[(w[i] / p) & 65535]--;
        }
}

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);
    countsort(aux, m, 65536);
}

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;
}