Cod sursa(job #2554290)

Utilizator KPP17Popescu Paul KPP17 Data 22 februarie 2020 19:24:29
Problema Radix Sort Scor 30
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.95 kb
#define fisier "radixsort"

#ifdef consola

    #include <iostream>
    #define in std::cin
    #define out std::cout

#else

    #include <fstream>

    #ifndef fisier
        #define fisier "HYPER"
    #endif

    std::ifstream in(fisier ".in");
    std::ofstream out(fisier ".out");

#endif



const int
MAX_N = 10000000, // 10 000 000
BAZA = 10;



inline int getCif(int x, int z) {

    return z > x?
    0:
    x / z % BAZA;

}



void cifSort(int* v, int n, int z) {

    static int frecv[BAZA], aux[MAX_N];

    for (int i = 0; i < n; i++) {

        frecv[getCif(v[i], z)] ++;

    }//out << '(';

    for (int cif = 1; cif < BAZA; cif++) {

        frecv[cif] += frecv[cif - 1];

        //out << frecv[cif] << ' ';

    }//out << ")\n\n";



    for (int cif = 0; cif < BAZA; cif++) {

        for (int i = n - 1; i >= 0; i--) {

            if (getCif(v[i], z) == cif) {

                aux[-- frecv[cif]] = v[i];

            }

        }

    }



    for (int cif = 0; cif < BAZA; cif++) {

        frecv[cif] = 0;

    }

    for (int i = 0; i < n; i++) {

        v[i] = aux[i];

    }


}



void radixSort(int* v, int n) {

    int z = 1, maxim = 1 << 31;

    for (int i = 0; i < n; i++) {

        if (v[i] > maxim) {

            maxim = v[i];

        }

    }

    while (z <= maxim) {

        //for (int i = 0; i < n; i++) {out << v[i] << ' ';} out << std::endl;

        cifSort(v, n, z);

        z *= BAZA;

    }//for (int i = 0; i < n; i++) {out << v[i] << ' ';} out << std::endl;

}



int v[MAX_N];

int main() {

    int n, a, b, c;

    in >> n >> a >> b >> c;

    *v = b;

    for (int i = 1; i < n; i++) {

        v[i] = (a * v[i - 1] + b) % c;

    }



    radixSort(v, n);



    for (int i = 0; i < n; i += 10) {

        out << v[i] << ' ';

    }

}






















//