Cod sursa(job #2551844)

Utilizator AvramDanielAvram Daniel AvramDaniel Data 20 februarie 2020 11:43:02
Problema Radix Sort Scor 30
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.34 kb
#include<bits/stdc++.h>
using namespace std;

const int baza = 100;
int a,b,c,n,v[10000010],temp[10000010], cnt[baza+1],mx,nr_max;

void countsort(int t){

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

    for(int i = 0;i<n;i++){
        cnt[(v[i]/t)%baza]++;
        temp[i] = 0;
    }

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

    }

    for(int i = n-1;i>=0;i--){
        temp[cnt[(v[i]/t)%baza] - 1] = v[i];
        cnt[(v[i]/t)%baza]--;
    }

    for(int i = 0;i<n;i++){
        v[i] = temp[i];
    }
}



void radixsort(){

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

    }





}



int main(){

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

            cout<<v[j]<<' ';

        }

        cout<<'\n';

{1}

    cout<<mx;*/

    while(mx){
        nr_max++;
        mx/=baza;
    }

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

}