Cod sursa(job #2561667)

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