Cod sursa(job #2775369)

Utilizator MarcGrecMarc Grec MarcGrec Data 15 septembrie 2021 15:29:53
Problema Radix Sort Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.2 kb
#define RADIX 8
#define DIGIT(x, i) (((x) >> ((i) * RADIX)) & ((1 << RADIX) - 1))

#include <iostream>
#include <fstream>
#include <vector>
#include <cstdint>
using namespace std;

ifstream fin("radixsort.in");
ofstream fout("radixsort.out");

int n, a, b, c;
vector<int> Buckets[2][1 << RADIX];

int main()
{
    fin >> n >> a >> b >> c;
    
    for (int64_t i = 1, x = b; i <= n; ++i, x = (a * x + b) % c)
    {
        Buckets[1][DIGIT(x, 0)].push_back(x);
    }
    
    {
        int i;
        for (i = 1; ((i - 1) * RADIX) <= ((int) sizeof(int)); ++i)
        {
            for (int mask = 0; mask < (1 << RADIX); ++mask)
            {
                for (int v : Buckets[i & 1][mask])
                {
                    Buckets[(i + 1) & 1][DIGIT(v, i)].push_back(v);
                }
            }
            
            for (int mask = 0; mask < (1 << RADIX); ++mask)
            {
                Buckets[i & 1][mask].clear();
            }
        }
        
        for (size_t i = 0; i < Buckets[i & 1][0].size(); i += 10)
        {
            fout << Buckets[i & 1][0][i] << ' ';
        }
    }
    
    fin.close();
    fout.close();
    return 0;
}