Cod sursa(job #2581711)

Utilizator PetrescuAlexandru Petrescu Petrescu Data 15 martie 2020 17:50:10
Problema Radix Sort Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.7 kb
#include <bits/stdc++.h>
#define MAX 10000000
#define NR_BUCKS 2
#define SIZE_BUCK 256

using namespace std;
typedef long long LL;

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

LL v[MAX + 5];
deque<int>bucks[NR_BUCKS][SIZE_BUCK];
int n, a, b, c;

void solve()
{
    for(int i = 1; i <= n; i++)
        v[i] = (a * v[i - 1] + b) % c;

    for(int i = 1; i <= n; i++)
        bucks[0][v[i] & (0x000000ff)].push_back(v[i]);

    for(int i = 0; i < SIZE_BUCK; i++)
        while(!bucks[0][i].empty())
        {
            int buckCurrentElem = bucks[0][i].front();
            bucks[1][(v[i] & (0x0000ff00)) >> 8].push_back(buckCurrentElem);
            bucks[0][i].pop_front();
        }

    for(int i = 0; i < SIZE_BUCK; i++)
        while(!bucks[1][i].empty())
        {
            int buckCurrentElem = bucks[1][i].front();
            bucks[0][(v[i] & (0x00ff0000)) >> 16].push_back(buckCurrentElem);
            bucks[1][i].pop_front();
        }

    for(int i = 0; i < SIZE_BUCK; i++)
        while(!bucks[0][i].empty())
        {
            int buckCurrentElem = bucks[0][i].front();
            bucks[1][(v[i] & (0xff000000)) >> 24].push_back(buckCurrentElem);
            bucks[0][i].pop_front();
        }

    int cnt = 0;
    for(int i = 0; i < SIZE_BUCK; i++)
        while(!bucks[1][i].empty())
        {
            if(cnt % 10 == 0)fout << bucks[1][i].front() << " ";
            bucks[1][i].pop_front();
            cnt++;
        }
}

int main()
{
    ios::sync_with_stdio(false);
    fin.tie(0);
    fout.tie(0);
    srand(time(NULL));

    fin >> n >> a >> b >> c;

    solve();

    fin.close();
    fout.close();

    return 0;
}