Cod sursa(job #2026237)

Utilizator SlevySlevoaca Stefan-Gabriel Slevy Data 23 septembrie 2017 23:22:24
Problema Radix Sort Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.3 kb
#include <iostream>
#include <fstream>
#include <cstring>
#define RADIX_SIZE 8
#define RADIX 0xff
#define TOTAL_BYTES 4
#define get_byte(x) ((x >> (byte * 8)) & RADIX)
#define NMAX 10000001

using namespace std;

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

int v[NMAX], n, a, b, c;

void count_sort(int A[], int B[], int byte) {

    int _count[1 << RADIX_SIZE];
    int index[1 << RADIX_SIZE];

    memset(_count, 0, sizeof(int) * (1 << RADIX_SIZE));

    for (int i = 1; i <= n; i++)
        _count[get_byte(A[i])]++;

    index[0] = 1;
    for (int i = 1; i < (1 << RADIX_SIZE); i++)
        index[i] = index[i - 1] + _count[i - 1];

    for (int i = 1; i <= n; i++)
        B[index[get_byte(A[i])]++] = A[i];
}

void radix_sort(int A[]) {

    int *temp = new int[n + 1];

    for (int byte = 0; byte < TOTAL_BYTES; ++byte) {

        if (byte & 1)
            count_sort(temp, A, byte);
        else
            count_sort(A, temp, byte);
    }

    delete[] temp;
}

int main() {

    in >> n >> a >> b >> c;
    in.close();

    v[1] = b;
    for (int i = 2; i <= n; i++)
        v[i] = (a * 1LL * v[i - 1] + b) % c;

    radix_sort(v);

    for (int i = 1; i <= n; i += 10)
        out << v[i] << " ";

    out.close();
    return 0;
}