Cod sursa(job #2094858)

Utilizator AkrielAkriel Akriel Data 26 decembrie 2017 17:20:57
Problema Radix Sort Scor 30
Compilator cpp Status done
Runda Arhiva educationala Marime 1.9 kb
#include <bits/stdc++.h>

#define formula 1LL*(components[0] * values[index] + components[1]) % components[2]
#define extractDigit (element / digitSelector) % 10;

using namespace std;

ifstream fin ("radixsort.in");
ofstream fout ("radixsort.out");

const int totalComponents = 3;
const int totalDigits = 10;

vector <long long> values;

int components[totalComponents];

int totalNumbers, mostSignificantDigit;

inline void readVariables(){
    fin >> totalNumbers;
    for ( int index = 0; index < totalComponents; index++ )
        fin >> components[index];

    values.push_back(components[1]);
    for ( int index = 0; index < totalNumbers-1; index++ )
        values.push_back(formula);
}

int determineStart(int number){
    int power = 1;
    for ( ; number; power*=10, number/=10);
    return power;
}

inline void displayAnswer(){
    for ( int element = 0; element < totalNumbers; element += 10 )
        fout << values[element] << " ";
}

inline void debbugingPurposes(vector <long long> values){
    for ( auto element : values )
        cerr << element << " ";
    cerr << "\n";
}

inline void radixSort(vector <long long> &values, int digitSelector = 1){
    if (digitSelector == 0 )
        return;

    vector <long long> buckets[totalDigits];

    for ( auto element : values ){
        int digit = extractDigit;
        buckets[digit].push_back(element);
    }

    for ( int digit = 0; digit < totalDigits; digit++ )
        if ( buckets[digit].size() )
            radixSort(buckets[digit], digitSelector/10);

    values.clear();
    for ( int digit = 0; digit < totalDigits; digit++ )
        for ( auto element : buckets[digit])
            values.push_back(element);
}

int main(){
    readVariables();
    mostSignificantDigit = determineStart(components[2]);
    radixSort(values, mostSignificantDigit);
    displayAnswer();
    return 0;
}