Cod sursa(job #2562575)

Utilizator AlexVulpoiuAlexandru Vulpoiu AlexVulpoiu Data 29 februarie 2020 15:41:23
Problema Radix Sort Scor 30
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.6 kb
#include <fstream>
#include <vector>
#include <cmath>
using namespace std;
ifstream f("radixsort.in");
ofstream g("radixsort.out");
int n, i;
long long int a, b, c, x;
vector<int> v;
void radixsort(vector<int> &vect)
{
    int i, j, max1;
    long long int p, q;
    vector<int> buck[256], newb[256];
    max1 = -1;
    for(i = 0; i < n; i++)
        max1 = max(max1, vect[i]);
    if(max1 > 0)
    {
        p = pow(256, floor(double(log2(max1) / 8)));
        for(i = 0; i < n; i++)
            buck[vect[i] % 256].push_back(vect[i]);
        q = 256;
        while(q <= p)
        {
            for(i = 0; i < 256; i++)
                newb[i].clear();
            for(i = 0; i < 256; i++)
                for(j = 0; j < buck[i].size(); j++)
                    newb[(buck[i][j] / q) % 256].push_back(buck[i][j]);
            for(i = 0; i < 256; i++)
            {
                buck[i].clear();
                for(j = 0; j < newb[i].size(); j++)
                    buck[i].push_back(newb[i][j]);
            }
            q *= 256;
        }
        vect.clear();
        for(i = 0; i < 256; i++)
            for(j = 0; j < buck[i].size(); j++)
                vect.push_back(buck[i][j]);
    }
}
int main()
{
    f >> n >> a >> b >> c;
    v.reserve(pow(10, 7));
    v.push_back(b);
    for(i = 1; i < n; i++)
    {
        x = (a * v[i - 1] + b) % c;
        v.push_back(x);
        if(v[i] < 0)
            v[i] += c;
    }
    f.close();
    radixsort(v);
    for(i = 0; i < n; i += 10)
        g << v[i] << " ";
    g << "\n";
    g.close();
    return 0;
}