Cod sursa(job #1802097)

Utilizator dumitrualexAlex Dumitru dumitrualex Data 9 noiembrie 2016 21:04:14
Problema Radix Sort Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.08 kb
#include <iostream>
#include <fstream>
#include <vector>
#define nmax 10000000+5
#define RADIX 0xFF
#define RADIX_SIZE 8
using namespace std;

int a[nmax], b[nmax];
int N, A, B, C;


void countsort(int * A, int * B, int byte)
{
    int i;
    int cnt[1<<RADIX_SIZE], start[1<<RADIX_SIZE];
    for (i = 0; i < (1 << RADIX_SIZE); i++)
        cnt[i] = 0;
    for (i = 0; i < N; i++)
        cnt[(A[i]>>(byte*8)) & RADIX]++;

    start[0] = 0;
    for (i = 1; i < (1 << RADIX_SIZE); i++)
        start[i] = start[i-1] + cnt[i-1];
    for (i = 0; i < N; i++)
        B[start[(A[i]>>(byte*8)) & RADIX]++] = A[i];

}
int main()
{
    ifstream fin("radixsort.in");
    ofstream fout("radixsort.out");

    int i;

    fin >> N >> A >> B >> C;

    a[0] = B % C;
    for (i = 1; i < N; i++)
        a[i] = (((1LL * A * a[i-1]) % C + B) % C);

    for (i = 0; i < sizeof(a[0]); i++)
        if (i % 2 == 0)
            countsort(a, b, i);
        else
            countsort(b, a, i);

    for (i = 0; i < N; i += 10)
        fout << a[i] << " ";
    return 0;
}