Cod sursa(job #2592149)

Utilizator Rares31100Popa Rares Rares31100 Data 1 aprilie 2020 12:10:09
Problema Radix Sort Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.02 kb
#include <bits/stdc++.h>
#define UI unsigned int
#define LL long long
#define Byte (1<<8)-1

using namespace std;

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

UI n,a[10000001],b[10000001];

void build()
{
    LL A,B,C;
    in>>A>>B>>C;
    a[1]=B;

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

int get_byte(int nr,int byte)
{
    return ( nr>>(byte*8) )&Byte;
}

void sortin(UI a[],UI b[],int byte)
{
    int Count[Byte+1],pozit[Byte+1];
    for(int i=0;i<=Byte;i++)
        Count[i]=0;

    for(int i=1;i<=n;i++)
        Count[get_byte(b[i],byte)]++;

    pozit[0]=0;
    for(int i=1;i<=Byte;i++)
        pozit[i]=pozit[i-1]+Count[i-1];

    for(int i=1;i<=n;i++)
        a[ ++pozit[get_byte(b[i],byte)] ]=b[i];
}

int main()
{
    in>>n;

    build();

    for(int byte=0;byte<=3;byte++)
        if(byte%2==0)
            sortin(b,a,byte);
        else
            sortin(a,b,byte);

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

    return 0;
}