Cod sursa(job #2119840)

Utilizator Alex18maiAlex Enache Alex18mai Data 1 februarie 2018 18:07:08
Problema Radix Sort Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.07 kb
#include <fstream>

using namespace std;

ifstream cin ("radixsort.in");
ofstream cout ("radixsort.out");

int v[10100100];
int aux[10100100];
int fv[300];

int main() {

    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    int n , a , b , c;
    cin>>n>>a>>b>>c;

    for (int i=1; i<=n; i++){
        long long nr = 1LL * v[i-1];
        nr *= 1LL * a;
        nr += 1LL * b;
        nr %= 1LL * c;
        v[i] = (int)nr;
    }

    for (long long bit = 0; bit < 31 ; bit += 8){

        for (int i=1; i<=n; i++){
            int nr = v[i] >> bit;
            nr &= 255;
            fv[nr]++;
        }

        for (int i=0; i<=255; i++){
            fv[i] += fv[i-1];
        }

        for (int i=n; i>=1; i--){
            int nr = v[i] >> bit;
            nr &= 255;
            aux[fv[nr]] = v[i];
            fv[nr]--;
        }

        for (int i=1; i<=n; i++){
            v[i] = aux[i];
        }

        for (int i=0; i<=255; i++){
            fv[i] = 0;
        }

    }

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

    return 0;
}