Cod sursa(job #1757916)

Utilizator meriniucrMeriniuc Razvan- Dumitru meriniucr Data 16 septembrie 2016 03:07:58
Problema Radix Sort Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.15 kb
#include <fstream>
#include <string.h>

int n;
int arr[10000000];
int temp[10000000];

void
sort(int a[],
     int b[],
     int i)
{
    int index;
    int counter[256];
    int j[256];

    memset(counter, 0, 1024);
    for (index = 0; index < n; ++index)
    {
        ++counter[(a[index] >> (8 * i)) & 0xFF];
    }

    j[0] = 0;
    for (index = 1; index < 256; ++index)
    {
        j[index] = j[index - 1] + counter[index - 1];
    }

    for (index = 0; index < n; ++index)
    {
        b[j[(a[index] >> (8 * i)) & 0xFF]++] = a[index];
    }
}

void
go()
{
    for (int index = 0; index < 4; ++index)
    {
        if (index & 1)
        {
            sort(temp, arr, index);
        }
        else
        {
            sort(arr, temp, index);
        }
    }
}

int main()
{
    std::ifstream mama("radixsort.in");
    std::ofstream tata("radixsort.out");
    long long a, b, c;

    mama >> n;
    mama >> a >> b >> c;

    arr[0] = b;

    for (int index = 1; index < n; ++index)
    {
        arr[index] = (a * arr[index - 1] + b) % c;
    }

    go();

    for (int index = 0; index < n; index += 10)
    {
        tata << arr[index] << ' ';
    }

    return 0;
}