Cod sursa(job #2095066)

Utilizator AkrielAkriel Akriel Data 26 decembrie 2017 21:14:36
Problema Radix Sort Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.67 kb
#include <bits/stdc++.h>

using namespace std;

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

#define formula (1LL * components[0] * values[index-1][0] + components[1]) % components[2]

const int maxNumbers = 1e7+5;
const int mask = (1<<8)-1;
const int totalLayers = 2;
const int maxCompoents = 3;

int values[maxNumbers][totalLayers];

int position[mask],
    components[maxCompoents];

int totalNumbers;

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

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

inline void radixSort(){
    for ( int shift = 0; shift <= 24; shift += 8 ){

        for ( int index = 1; index <= totalNumbers; index++ ){
            position[(values[index][0] >> shift) & mask]++;
        }

        for ( int index = 1; index <= mask; index++ ){
            position[index] += position[index-1];
        }

        for ( int index = totalNumbers; index >= 1; index-- ){
            values[position[(values[index][0] >> shift) & mask]--][1] = values[index][0];
        }

        for ( int bits = 0; bits <= mask; bits++ ){
            position[bits] = 0;
        }

        for ( int index = 1; index <= totalNumbers; index++ ){
            values[index][0] = values[index][1];
        }
    }
}

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

int main(){
    readVariables();
    radixSort();
    displayAnswer();
    return 0;
}