Cod sursa(job #2268621)

Utilizator SqueekDanielTodasca Daniel SqueekDaniel Data 25 octombrie 2018 00:42:59
Problema Radix Sort Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.07 kb
#include <bits/stdc++.h>

#define MaxN 10000005

std::ifstream InFile("radixsort.in");
std::ofstream OutFile("radixsort.out");

int N, A, B, C;
int V[MaxN];

inline int GetBits(int x, int nbytes) {
    return (x >> (8*nbytes)) & 255;
}

int Aux[MaxN];
int DigitCount[256];

void CountSort(int byte) {
    for (int i=1; i<=N; ++i)
        DigitCount[GetBits(V[i], byte)] ++;

    for (int i=1; i<=255; ++i)
        DigitCount[i] += DigitCount[i-1];

    for (int i=N, Digit; i>0; --i) {
        Digit = GetBits(V[i], byte);
        Aux[DigitCount[Digit]] = V[i];
        --DigitCount[Digit];
    }

    for (int i=1; i<=N; ++i)
        V[i] = Aux[i];
}

void Radix() {
    for (int byte=0; byte<4; ++byte)
        CountSort(byte);
}

void Citire() {
    InFile >> N >> A >> B >> C;

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

void Rezolvare() {
    Radix();

    for (int i=1; i<=N; i+=10)
        OutFile << V[i] << ' ' ;
}

int main()
{
    Citire();
    Rezolvare();

    return 0;
}