Cod sursa(job #2581467)

Utilizator Mirela_MagdalenaCatrina Mirela Mirela_Magdalena Data 15 martie 2020 12:52:23
Problema Radix Sort Scor 30
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.37 kb
#include <cstdio>
#include <iostream>
#include <vector>
#include <bits/stdc++.h>
using namespace std;

int n, a, b, c;
vector<int> v, aux;

#define TOTAL_BYTES sizeof(v[1])
#define RADIX 0xFF
#define RADIX_SIZE 8
#define get_byte(x) (x>>(8*byte) & RADIX)


void formv()
{
    aux.resize(n+5);
    v.resize(n+5);
    v[0] = b;
    for(int i = 1; i < n; ++i)
    {
        int val = ((1LL*v[i-1]*a)%c + b)%c;
        v[i] = val;
    }
}

void afis(int step)
{
    for(int i = 0; i < n; i += step)
        printf("%d ", v[i]);
}

void countSort(vector<int> &v, vector<int> &aux, int byte)
{
    int counter[1 << RADIX_SIZE];
    int index[1 << RADIX_SIZE];

    memset(counter, 0, sizeof(counter));

    for(int i = 0; i < n; ++i)
        counter[get_byte(v[i])]++;

    index[0] = 0;
    for(int i = 1; i < 1<<RADIX_SIZE; ++i)
        index[i] = index[i-1] + counter[i-1];

    for(int i = 0; i < n; ++i)
        aux[index[get_byte(v[i])]++] = v[i];


}


void radix()
{
    for(int i = 0; i < TOTAL_BYTES; ++i)
        if(i%2 == 0)
            countSort(v, aux, i);
        else countSort(aux, v, i);
}

void read()
{
    scanf("%d %d %d %d", &n, &a, &b, &c);
    formv();
}

int main()
{
    freopen("radixsort.in", "r", stdin);
    freopen("radixsort.out", "w", stdout);
    read();
    radix();
    afis(10);
    return 0;
}