Cod sursa(job #2224896)

Utilizator andreisontea01Andrei Sontea andreisontea01 Data 25 iulie 2018 14:32:20
Problema Radix Sort Scor 30
Compilator cpp Status done
Runda Arhiva educationala Marime 1.46 kb
#include <iostream>
#include <fstream>
#include <vector>

using namespace std;

const int MAXBIT = 1 << 8;

vector<int> bucket1[MAXBIT], bucket2[MAXBIT], bucket3[MAXBIT], bucket4[MAXBIT];

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