Cod sursa(job #2672838)

Utilizator zarg169Roxana zarg169 Data 15 noiembrie 2020 01:25:44
Problema Radix Sort Scor 30
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.47 kb
#include <iostream>
#include <fstream>
#include <vector>

using namespace std;
int v[10000005];
vector<int> hashtable[10001];

int main()
{
    ifstream fin("radixsort.in");
    ofstream fout("radixsort.out");
    int n, a, b, c, key, nrDigits = 0, maxim = 0;
    fin >> n >> a >> b >> c;

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

    for (int i = 1; i <= n; ++i) {
        if (maxim <= v[i]){
            maxim = v[i];
        }
    }
    while (maxim != 0) {
        maxim = maxim / 10;
        nrDigits += 1;
    }

    int r;
    if (nrDigits % 4 != 0) {
        r = nrDigits / 4 + 1;
    } else {
        r = nrDigits / 4;
    }

    int step = 1;

    while (step <= r) {
        int z = 1;
        int t = 1;
        while (t < step) {
            z *= 10000;
            t += 1;
        }
        for (int i = 1; i <= n; ++i) {
            int x = (v[i] / z) % 10000;
            key = x;
            hashtable[key].push_back(v[i]);
        }

        int d = 1;
        for (int j = 0; j <= 9999; ++j) {
            if (hashtable[j].size() != 0) {
                for (int i = 0; i < hashtable[j].size(); ++i) {
                    v[d] = hashtable[j][i];
                    d += 1;
                }
            }
            hashtable[j].clear();
        }
        step += 1;
    }

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