Cod sursa(job #2886670)

Utilizator Mihai_EduardMihai Eduard Mihai_Eduard Data 8 aprilie 2022 00:53:46
Problema Radix Sort Scor 30
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.1 kb
#include <bits/stdc++.h>

using namespace std;

ifstream fin("radixsort.in");
ofstream fout("radixsort.out");
const int NMAX=10000005;
const int total_bytes=4;

///impartim numerele in 4 bucket-uri de cate un byte si le sortam incepand cu cea mai putin semnificativa parte
int N, v[NMAX], a, b, c, baza=(1<<8), aux[NMAX];

void countSort(int v[], int aux[], int byte){
    int cnt[baza]={}, index[baza]={};

    for(int i=1;i<=N;i++)
        cnt[(v[i]>>(byte*8))&(baza-1)]++;

    index[0]=0;
    for(int i=1;i<baza;i++)
        index[i]=index[i-1]+cnt[i-1];

    for(int i=1;i<=N;i++)
        aux[++index[(v[i]>>(byte*8))&(baza-1)]]=v[i];
}

void radixSort(int v[]){
    for(int i=0;i<4;i++){
        ///sortam dupa byte-ul i
        if(i%2==0)
            countSort(v,aux,i);
        else
            countSort(aux,v,i);
    }
}

int main()
{
    fin>>N;
    fin>>a>>b>>c;
    v[1]=b;
    for(int i=2;i<=N;i++)
        v[i]=(1LL*a*v[i-1]%c+b)%c;

    radixSort(v);

    for(int i=1;i<=N;i+=10)
        fout<<v[i]<<' ';

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