Cod sursa(job #2607418)

Utilizator theodor.moroianuTheodor Moroianu theodor.moroianu Data 29 aprilie 2020 18:42:10
Problema Radix Sort Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.18 kb
#include <bits/stdc++.h>
using namespace std;

void RSort(vector <int> & v)
{
    const int N = (1 << 16);
    const int mask = (1 << 16) - 1;
    vector <int> head(N, -1), val(N), urm(N);

    for (int i = 0; i < (int)v.size(); i++) {
        urm[i] = head[v[i] & mask];
        val[i] = v[i];
        head[v[i] & mask] = i;
    }

    v.clear();
    for (int i = N - 1; i >= 0; i--) {
        while (head[i] != -1) {
            v.push_back(val[head[i]]);
            head[i] = urm[head[i]];
        }
    }

    for (int i = 0; i < (int)v.size(); i++) {
        urm[i] = head[v[i] >> 16];
        val[i] = v[i];
        head[v[i] >> 16] = i;
    }

    v.clear();
    for (int i = 0; i < N; i++) {
        while (head[i] != -1) {
            v.push_back(val[head[i]]);
            head[i] = urm[head[i]];
        }
    }
}

int main()
{
    ifstream in("radixsort.in");
    ofstream out("radixsort.out");
    
    int n, a, b, c;
    in >> n >> a >> b >> c;
    
    vector <int> ans(n);
    ans[0] = b;
    for (int i = 1; i < n; i++)
        ans[i] = (1LL * ans[i - 1] * a + b) % c;

    RSort(ans);

    for (int i = 0; i < n; i += 10)
        out << ans[i] << ' ';
    
    out << '\n';
    return 0;
}