Cod sursa(job #2762968)

Utilizator cezar_titianuTitianu Cezar cezar_titianu Data 10 iulie 2021 15:48:20
Problema Radix Sort Scor 70
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.4 kb
#include <fstream>
#include <vector>
#include <cstring>

#define BASE 8

void radix_sort(std::vector <int>& vec) {
    std::vector <int> sec = vec;
    std::vector <int>::iterator mat[2] = { vec.begin(), sec.begin() };
    int frec[1 << BASE];
    int part[1 << BASE];
    int pos;
    for (int index = 0; index < 32 / BASE; index++) {
        memset(frec, 0, sizeof(frec));
        for (int index2 = 0; index2 < (int)vec.size(); index2++) {
            frec[(mat[index & 1][index2] >> (index * BASE)) & ((1 << BASE) - 1)]++;
        }
        part[0] = 0;
        for (int index2 = 1; index2 < (1 << BASE); index2++) {
            part[index2] = part[index2 - 1] + frec[index2 - 1];
        }
        for (int index2 = 0; index2 < (int)vec.size(); index2++) {
            pos = (mat[index & 1][index2] >> (index * BASE)) & ((1 << BASE) - 1);
            mat[!(index & 1)][part[pos]++] = mat[index & 1][index2];
        }
    }
}

int main() {
    std::ifstream fin("radixsort.in");
    std::ofstream fout("radixsort.out");
    std::vector <int> vec;
    int nrn, nra, nrb, nrc;
    fin >> nrn >> nra >> nrb >> nrc;
    vec.push_back(nrb);
    for (int index = 1; index < nrn; index++) {
        vec.push_back(((long long int)nra * vec.back() + nrb) % nrc);
    }
    radix_sort(vec);
    for (int index = 0; index < (int)vec.size(); index += 10) {
        fout << vec[index] << " ";
    }
}