Cod sursa(job #1114035)

Utilizator Stefex09Stefan Teodorescu Stefex09 Data 21 februarie 2014 10:49:36
Problema Radix Sort Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.02 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], B[MAXN];

void radix (int *A, int *B, const int byte)
{
    int i;
    int Cnt[mask + 1], Ind[mask + 1];
    memset (Cnt, 0, sizeof (Cnt));

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

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

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

void radix_sort ()
{
    radix (V, B, 0);
    radix (B, V, 8);
    radix (V, B, 16);
    radix (B, V, 24);
}

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

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

    radix_sort ();

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

    return 0;
}