Cod sursa(job #3124417)

Utilizator daristyleBejan Darius-Ramon daristyle Data 28 aprilie 2023 16:50:49
Problema Radix Sort Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.08 kb
#include <fstream>

using namespace std;

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

const int N_MAX=1e7;
const int BIT_MAX=30;
int v[N_MAX];

void RadixSort(int v[], int begin, int end, int bit){//MSD
    if(end<=begin || bit<0)
        return;

    int b=begin, e=end;
    while(b<end && (v[b]&(1<<bit))==0)
        ++b;
    while(e>begin && (v[e]&(1<<bit))>0)
        --e;
    while(b<=e){
        int aux=v[b];
        v[b]=v[e];
        v[e]=aux;
        do
            ++b;
        while(b<end && (v[b]&(1<<bit))==0);
        do
            --e;
        while(e>begin && (v[e]&(1<<bit))>0);
    }

    b=begin;
    while(b<=end && (v[b]&(1<<bit))==0)
        ++b;

    RadixSort(v, begin, b-1, bit-1);
    RadixSort(v, b, end, bit-1);
}

int main() {
    int n, a, b, c;
    fin>>n>>a>>b>>c;
    v[0]=b;
    for(int i=1; i<n; ++i)
        v[i]=(a*v[i-1]+b)%c;

    RadixSort(v,0, n-1, BIT_MAX);

    for(int i=0; i<n; ++i)
        fout<<v[i]<<' ';
    fout.put('\n');

    fin.close();
    fout.close();
    return 0;
}