Cod sursa(job #2356304)

Utilizator andreiomd1Onut Andrei andreiomd1 Data 26 februarie 2019 16:48:51
Problema Radix Sort Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.22 kb
#include <bits/stdc++.h>

#define RADIX 0xFF

#define get_byte(x) ((x>>(byte * 8))&RADIX)

using namespace std;

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

const int NMAX=1e7+5;

int N, A, B, C;

int V[NMAX];

inline void Read ()
{
    f.tie(NULL);

    f>>N>>A>>B>>C;

    V[1]=B;

    for(int i=2; i<=N; ++i)
        V[i]=(1LL*A*V[i-1]+B)%C;

    return;
}

inline void Count_Sort (int A[], int B[], int byte)
{
    int cnt[256];
    int ord[256];

    memset(cnt, 0, sizeof(cnt));
	memset(ord, 0, sizeof(ord));

    for(int i=1; i<=N; ++i)
        ++cnt[get_byte(A[i])];

    ord[0]=0;

    for(int i=1; i<256; ++i)
        ord[i]=ord[i-1]+cnt[i-1];

    for(int i=1; i<=N; ++i)
        B[++ord[get_byte(A[i])]]=A[i];

    return;
}

inline void Sort ()
{
    int temp[N+5];

    memset(temp, 0, sizeof(temp));

    int Total=sizeof(V[1]);

    for(int i=0; i<Total; ++i)
        if(i % 2 == 0)
            Count_Sort(V, temp, i);
        else Count_Sort(temp, V, i);

    return;
}

inline void Write ()
{
    for(int i=1; i<=N; i+=10)
        g<<V[i]<<' ';

    exit(0);
}

int main()
{
    Read();

    Sort();

    Write();

    return 0;
}