Cod sursa(job #2229386)

Utilizator rnqftwcalina florin daniel rnqftw Data 6 august 2018 17:40:49
Problema Radix Sort Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 1.2 kb
#include<bits/stdc++.h>

using namespace std;
#define N_Max 10000007
int v[N_Max];
int vectorAux[N_Max];

void printArray(int array[],int n){

    for(int i = 1 ; i <= n ; i++)
        cout << array[i] << " ";
    cout << endl;
}

void radixSort(int n){
    ofstream out("radixsort.out");
    ios::sync_with_stdio(false);
    out.tie(0);
    int mask = (1<<16)-1;
    for(int bits = 0 ; bits < 32 ; bits += 16){
        int counting[1<<16+5] = {0};
        for(int i = 1 ; i <= n ; i++)
            counting[(v[i]>>bits)&mask]++;

        for(int i = 1 ; i <= mask ; i++)
            counting[i] += counting[i-1];

        for(int i = n ; i >= 1 ; i -- ){
            vectorAux[counting[(v[i]>>bits)&mask]--] = v[i];
        }

        for(int i = 1 ; i <= n ; i ++ )
            v[i] = vectorAux[i];



    }
    for(int i = 1 ; i <= n ; i += 10)
        out << v[i] << " ";

}
int main(){

    int n , a ,b , c;
    ifstream in("radixsort.in");
    ios::sync_with_stdio(false);
    in.tie(0);
    in >> n >> a >> b >>c;
    v[1] = b ;
    for(int i = 2 ; i <= n ; i++){
        int newValue = (1LL * a * v[i - 1] + b) % c;
        v[i] = newValue;
    }
    radixSort(n);

}