Cod sursa(job #2225391)

Utilizator andreisontea01Andrei Sontea andreisontea01 Data 26 iulie 2018 20:56:16
Problema Radix Sort Scor 30
Compilator cpp Status done
Runda Arhiva educationala Marime 1.22 kb
#include <iostream>
#include <fstream>
#include <vector>

using namespace std;

const int MAXBIT = 1 << 9;

vector<int> bucket[MAXBIT];
int num[10000005];

long long mask;
int index, n;

void rsort(int pow){
    mask <<= 8;
    for(int i = 1; i <= n; ++i){
        int pos = num[i] & mask;
        pos >>= pow;
        bucket[pos].push_back(num[i]);
    }
    index = 1;
    for(int i = 0; i <= 1 << 8; ++i){
        for(int j = 0; j < int(bucket[i].size()); ++j)
            num[index++] = bucket[i][j];
        bucket[i].clear();
    }
}

int main()
{
    ifstream fin("radixsort.in");
    ofstream fout("radixsort.out");
    int a, b, c;
    fin >> n >> a >> b >> c;
    num[1] = b;
    for(int i = 2; i <= n; ++i)
        num[i] = (a * num[i - 1] + b) % c;
    mask = (1LL << 8) - 1;
    for(int i = 1; i <= n; ++i){
        long long pos = num[i] & mask;
        bucket[pos].push_back(num[i]);
    }
    index = 1;
    for(int i = 0; i <= 1 << 8; ++i){
        for(int j = 0; j < int(bucket[i].size()); ++j)
            num[index++] = bucket[i][j];
        bucket[i].clear();
    }
    rsort(8);
    rsort(16);
    rsort(32);
    for(int i = 1; i <= n; ++i){
        if(i % 10 == 1)
            fout << num[i] << " ";
    }
    return 0;
}