Cod sursa(job #2561662)

Utilizator AlexVulpoiuAlexandru Vulpoiu AlexVulpoiu Data 29 februarie 2020 01:24:58
Problema Radix Sort Scor 30
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.48 kb
#include <fstream>
#include <vector>
#include <cmath>
using namespace std;
ifstream f("radixsort.in");
ofstream g("radixsort.out");
int n, a, b, c, i, v[10000000];
void copiere(vector<int> v1[256], vector<int> v2[256])
{
    int i, j;
    for(i = 0; i < 256; i ++)
    {
        v1[i].clear();
        for(j = 0; j < v2[i].size(); j ++)
            v1[i].push_back(v2[i][j]);
    }
}
void radixsort(int vect[10000000])
{
    int i, j, p, q, max1;
    vector<int> buck[256], newb[256];
    max1 = -1;
    for(i = 0; i < n; i ++)
        if(vect[i] > max1)
            max1 = vect[i];
    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]);
        copiere(buck, newb);
        q *= 256;
    }
    p = 0;
    for(i = 0; i < 256; i ++)
        for(j = 0; j < buck[i].size(); j ++)
            vect[p ++] = buck[i][j];
}
int main()
{
    f >> n >> a >> b >> c;
    v[0] = b;
    for(i = 1; i < n; i ++)
    {
        v[i] = (a * v[i - 1] + b) % c;
        if(v[i] < 0)
            v[i] = -v[i];
    }
    f.close();
    radixsort(v);
    for(i = 0; i < n; i += 10)
        g << v[i] << " ";
    g << "\n";
    g.close();
    return 0;
}