Cod sursa(job #3155264)

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

using namespace std;

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

vector<unsigned int> buckets[2];
vector<unsigned int> newBuckets[2];
unsigned int maxi=0;

void radixSort()
{
    unsigned int p=1;

    while((1<<p)<=maxi)
    {
        for(unsigned int i=0;i<buckets[0].size();i++)
            newBuckets[(buckets[0][i]>>p)&1].push_back(buckets[0][i]);
        for(unsigned 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 main() {

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

    buckets[b&1].push_back(b);
    unsigned int last=b;
    for(unsigned int i=1;i<n;i++)
    {
        unsigned int x=(a*last+b)%c;
        buckets[x&1].push_back(x);
        last=x;
        maxi=max(maxi, x);
    }

    radixSort();

    for(unsigned int i=0;i<buckets[0].size();i+=10)
        out<<buckets[0][i]<<' ';
    for(unsigned int i= 10-(buckets[0].size()-1)%10-1  ;i<buckets[1].size();i+=10)
        out<<buckets[1][i]<<' ';

    return 0;
}