Cod sursa(job #1736925)

Utilizator AlexandruValeanuAlexandru Valeanu AlexandruValeanu Data 2 august 2016 21:59:34
Problema Radix Sort Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.47 kb
#include <bits/stdc++.h>

using namespace std;

class RadixSort
{
private:

    static const int MAX_DIGITS = 8;
    static const int RADIX = (1 << MAX_DIGITS);
    static const int MASK = RADIX - 1;

public:

    static void sort(vector<int> &A)
    {
        vector<int> B(A.size());
        vector<int> buckets(RADIX);

        const int N = A.size();

        for (int shift = 0; shift < 32; shift += MAX_DIGITS)
        {
            fill(buckets.begin(), buckets.end(), 0);

            for (int v : A)
                ++buckets[(v >> shift) & MASK];

            partial_sum(buckets.begin(), buckets.end(), buckets.begin());

            for (int i = N - 1; i >= 0; --i)
                B[--buckets[(A[i] >> shift) & MASK]] = A[i];

            copy(B.begin(), B.end(), A.begin());
        }
    }
};

void printNumber(int nr, string &output)
{
    char digits[10];
    int n = 0;

    do
    {
        digits[n++] = '0' + nr % 10;
        nr /= 10;

    } while (nr > 0);

    for (int i = n - 1; i >= 0; i--)
        output += digits[i];

    output += " ";
}

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

    int N, A, B, C;
    in >> N >> A >> B >> C;

    vector<int> v(N);
    v[0] = B;

    for (int i = 1; i < N; ++i)
    {
        int t = (1LL * A * v[i - 1] + B) % C;
        v[i] = t;
    }

    RadixSort::sort(v);

    string output;

    for (int i = 0; i < N; i += 10)
        printNumber(v[i], output);

    out << output << endl;

    return 0;
}