Cod sursa(job #2581723)

Utilizator PetrescuAlexandru Petrescu Petrescu Data 15 martie 2020 18:18:55
Problema Radix Sort Scor 30
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.82 kb
#include <bits/stdc++.h>
#define MAX 10000000
#define NR_bucketet 2
#define SIZE_bucket 256

using namespace std;

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

int v[MAX + 5];
deque<int>bucketet[NR_bucketet][SIZE_bucket + 5];
int n, a, b, c;

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

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

    for(int i = 0; i < SIZE_bucket; i++)
        while(!bucketet[0][i].empty())
        {
            int bucketetCurrentElem = bucketet[0][i].front();
            bucketet[1][(bucketetCurrentElem & (0x0000ff00)) >> 8].push_back(bucketetCurrentElem);
            bucketet[0][i].pop_front();
        }

    for(int i = 0; i < SIZE_bucket; i++)
        while(!bucketet[1][i].empty())
        {
            int bucketCurrentElem = bucketet[1][i].front();
            bucketet[0][(bucketCurrentElem & (0x00ff0000)) >> 16].push_back(bucketCurrentElem);
            bucketet[1][i].pop_front();
        }

    for(int i = 0; i < SIZE_bucket; i++)
        while(!bucketet[0][i].empty())
        {
            int bucketCurrentElem = bucketet[0][i].front();
            bucketet[1][(bucketCurrentElem & (0xff000000)) >> 24].push_back(bucketCurrentElem);
            bucketet[0][i].pop_front();
        }

    int cnt = 0;
    for(int i = 0; i < SIZE_bucket; i++)
        while(!bucketet[1][i].empty())
        {
            if(cnt % 10 == 0)fout << bucketet[1][i].front() << " ";
            bucketet[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;
}