Cod sursa(job #2471467)

Utilizator andreisontea01Andrei Sontea andreisontea01 Data 10 octombrie 2019 23:32:33
Problema Radix Sort Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.21 kb
#include <iostream>
#include <fstream>
#include <vector>

using namespace std;

const int MAXN = 10000005;

int num[MAXN], sorted[MAXN], bucket[1 << 17];

int n;

void rsort(int bucksize, int nobuck){
    int mask = (1 << 16) - 1, lim = 1 << 16;
    for(int i = 0; i < lim; ++i)
        bucket[i] = 0;
    for(int i = 1; i <= n; ++i){
        int pos = (num[i] >> (bucksize * nobuck)) & mask;
        bucket[pos]++;
    }
    for(int i = 1; i < lim; ++i)
        bucket[i] += bucket[i - 1];
    for(int i = n; i >= 1; --i){
        int pos = (num[i] >> (bucksize * nobuck)) & mask;
        sorted[bucket[pos]] = num[i];
        bucket[pos]--;
    }
    for(int i = 1; i <= n; ++i)
        num[i] = sorted[i];
}

int main()
{
    ifstream fin("radixsort.in");
    ofstream fout("radixsort.out");
    ios::sync_with_stdio(false);
    fin.tie(0);
    fout.tie(0);
    int a, b, c;
    fin >> n >> a >> b >> c;
    num[1] = b;
    for(int i = 2; i <= n; ++i){
        int val = static_cast<int>((1LL * a * num[i - 1] + b) % c);
        num[i] = val;
    }
    for(int i = 0; i <= 1; ++i)
        rsort(16, i);
    for(int i = 1; i <= n; i += 10)
        fout << num[i] << " ";
    return 0;
}