Cod sursa(job #3155252)

Utilizator GrigMihaiGrigore Mihai GrigMihai Data 7 octombrie 2023 19:05:58
Problema Radix Sort Scor 30
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.22 kb
#include <fstream>
#include <vector>

using namespace std;

ifstream in("radixsort.in");
ofstream out("radixsort.out");

void radixSort(vector<unsigned int>& v)
{
    vector<unsigned int> buckets[2];
    vector<unsigned int> newBuckets[2];


    unsigned int p=1;
    unsigned int maxi=0;
    for(int i=0;i<v.size();i++)
    {
        buckets[v[i]&p].push_back(v[i]);
        maxi=max(maxi, v[i]);
    }

    while((1<<p)<=maxi)
    {
        for(int i=0;i<buckets[0].size();i++)
            newBuckets[(buckets[0][i]>>p)&1].push_back(buckets[0][i]);
        for(int i=0;i<buckets[1].size();i++)
            newBuckets[(buckets[1][i]>>p)&1].push_back(buckets[1][i]);

        buckets[0]=newBuckets[0];
        buckets[1]=newBuckets[1];

        newBuckets[0].clear();
        newBuckets[1].clear();

        p++;
    }

    int m=0;
    for(int i=0;i<buckets[0].size();i++)
        v[m++]=buckets[0][i];
    for(int i=0;i<buckets[1].size();i++)
        v[m++]=buckets[1][i];
}

int main() {

    unsigned int n, a, b, c;
    in>>n>>a>>b>>c;

    vector<unsigned int> v;
    v.push_back(b);

    for(int i=1;i<n;i++)
        v.push_back((a*v[i-1]+b)%c);

    radixSort(v);

    for(int i=0;i<v.size();i+=10)
        out<<v[i]<<' ';

    return 0;
}