Cod sursa(job #1339382)

Utilizator Edsger.DijkstraEdsger Wybe Dijkstra Edsger.Dijkstra Data 10 februarie 2015 21:03:19
Problema Radix Sort Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.97 kb
#include <iostream>
#include <fstream>
#include <cstring>

using namespace std;

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

const int MAXN = 10000010;
const int mask = (1 << 8) - 1;

int N;
int V[MAXN], W[MAXN];

void radix (int *A, int *B, const int &byte)
{
    int i;
    int Bucket[mask + 1], Cnt[mask + 1];

    memset (Bucket, 0, sizeof (Bucket));

    for (i = 1; i <= N; i ++)
        Bucket[(A[i] >> byte) & mask] ++;

    Cnt[0] = 1;
    for (i = 1; i <= mask; i ++)
        Cnt[i] = Cnt[i - 1] + Bucket[i - 1];

    for (i = 1; i <= N; i ++)
        B[Cnt[(A[i] >> byte) & mask] ++] = A[i];
}

int main()
{
    int A, B, C, i;

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

    radix (V, W, 0);
    radix (W, V, 8);
    radix (V, W, 16);
    radix (W, V, 24);

    for (i = 1; i <= N; i += 10)
        out << V[i] << " ";

    return 0;
}