Cod sursa(job #2522008)

Utilizator SochuDarabaneanu Liviu Eugen Sochu Data 11 ianuarie 2020 20:23:28
Problema Radix Sort Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.04 kb
#include <bits/stdc++.h>
#define N 10000005
#define Get_Byte(x , byte) ( (x >> (byte * 8)) & ((1 << 8) - 1) )

using namespace std;

ifstream f ("radixsort.in");
ofstream g ("radixsort.out");

int n , A , B , C;
int a[N] , countt[260] , output[N];

void CountSort(int exp , int a[] , int output[])
{
    memset(countt , 0 , sizeof(countt));

    int i;

    for(i = 1 ; i <= n ; i++)
        ++countt[Get_Byte(a[i] , exp)];

    for(i = 1 ; i <= 256 ; i++)
        countt[i] += countt[i - 1];

    for(i = n ; i >= 1 ; i--)
        output[ countt[Get_Byte(a[i] , exp)]-- ] = a[i];
}

void RadixSort()
{
    for(short bucket = 0 ; bucket < 4 ; bucket++)
        if(bucket % 2 == 0)
            CountSort(bucket , a , output);
        else CountSort(bucket , output , a);
}

int main()
{
    int i;

    f >> n >> A >> B >> C;

    a[1] = B;

    for(i = 2 ; i <= n ; i++)
        a[i] = (1ll * A * a[i - 1] + B) % C;

    RadixSort();

    for(i = 1 ; i <= n ; i += 10)
        g << a[i] << ' ';

    return 0;
}