Cod sursa(job #1685124)

Utilizator bogdan10bosBogdan Sitaru bogdan10bos Data 11 aprilie 2016 15:23:41
Problema Radix Sort Scor 30
Compilator cpp Status done
Runda Arhiva educationala Marime 1.15 kb
#include <bits/stdc++.h>

using namespace std;

#define FILE_IO

int N, A, B, C;
int v[1000005];
int aux[1000005];
int cnt[305], done[305];

void srt(int lft, int rgt)
{
    int msk = 0;
    for(int i = lft; i <= rgt; i++)
        msk ^= (1 << i);

    for(int i = 0; i <= 255; i++)
        cnt[i] = done[i] = 0;

    for(int i = 1; i <= N; i++)
        cnt[ (v[i] & msk) >> lft ]++;
    for(int i = 1; i <= 255; i++)
        cnt[i] += cnt[i - 1];

    for(int i = 1; i <= N; i++)
    {
        done[ (v[i] & msk) >> lft ] ++;
        int idx = cnt[ ( (v[i] & msk) >> lft ) - 1 ] + done[ (v[i] & msk) >> lft ];
        aux[ idx ] = v[i];
    }
    for(int i = 1; i <= N; i++)
        v[i] = aux[i];
}

int main()
{
    #ifdef FILE_IO
    freopen("radixsort.in", "r", stdin);
    freopen("radixsort.out", "w", stdout);
    #endif

    scanf("%d%d%d%d", &N, &A, &B, &C);
    v[1] = B;
    for(int i = 2; i <= N; i++)
        v[i] = ( (1LL * v[i - 1] * A) % C + B ) % C;

    srt(0, 7);
    srt(8, 15);
    srt(16, 23);
    srt(24, 31);

    for(int i = 1; i <= N; i += 10)
        printf("%d ", v[i]);

    return 0;
}