Cod sursa(job #2557604)

Utilizator AvramDanielAvram Daniel AvramDaniel Data 25 februarie 2020 21:39:34
Problema Radix Sort Scor 30
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.43 kb
#include<bits/stdc++.h>
using namespace std;

const int baza = 256;
int a,b,c,n,v[2][10000010], cnt[baza+1],mx,nr_max;
bool linie;
void countsort(int t){

    for(int i = 0;i<=baza;i++){
        cnt[i] = 0;
    }

    for(int i = 0;i<n;i++){
        cnt[(v[linie][i] >> t) & (baza-1)]++;
        v[!linie][i] = 0;
    }

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

    }

    for(int i = n-1;i>=0;i--){
        v[!linie][cnt[(v[linie][i] >> t) & (baza - 1)] - 1] = v[linie][i];
        cnt[(v[linie][i] >> t) & (baza - 1)]--;
    }

    linie = !linie;
    return;
}



void radixsort(){

    int exp = 0;
    for(int i = 1;i<=nr_max;i++){
        countsort(exp);
      /*  for(int j = 0;j<n;j++){
            cout<<v[j]<<' ';
        }
        cout<<'\n';*/
        exp +=8;
    }
    return;
}

int main(){

    ifstream cin("radixsort.in");
    ofstream cout("radixsort.out");
    cin>>n>>a>>b>>c;
    v[linie][0] = b;
    mx = b;
    for(int i = 1;i<n;i++){
        v[linie][i] = (a*v[linie][i-1] + b)%c;
        mx = max(mx, v[linie][i]);
    }
    /*for(int j = 0;j<n;j++){
{1}
            cout<<v[j]<<' ';
{1}
        }
{1}
        cout<<'\n';
{1}
{1}
{1}
    cout<<mx;*/

    while(mx){
        nr_max++;
        mx >>= 8;
    }

    //cout<<' '<<nr_max<<'\n';
    radixsort();
    for(int i = 0;i<n;i+=10)
        cout<<v[linie][i]<<' ';
    return 0;

}