Cod sursa(job #2225265)

Utilizator andreisontea01Andrei Sontea andreisontea01 Data 26 iulie 2018 14:55:16
Problema Radix Sort Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.76 kb
#include <iostream>
#include <fstream>
#include <vector>

using namespace std;

const int MAXBIT = 1 << 9;

vector<int> bucket[MAXBIT], num;

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