Cod sursa(job #1842202)

Utilizator bt.panteaPantea Beniamin bt.pantea Data 6 ianuarie 2017 17:23:06
Problema Radix Sort Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.04 kb
#include <iostream>
#include <fstream>
#include <cstring>
#define NMAX 10000010
#define GetBit(x) (x & 1<<byte) != 0 ? 1 : 0
#define RADIX 0xFF
#define get_byte(x) ((x>>(byte * 8)) & RADIX)
using namespace std;
ifstream f ("radixsort.in");
ofstream g ("radixsort.out");

int v[2][NMAX], n, a, b, c;
int sw = 0;

void CountSort(int a[], int b[], int byte)
{
    int counter[256], index[256];
    memset(counter, 0, sizeof(counter));

    for (int i = 0; i < n; i++)
        counter[get_byte(a[i])]++;
    index[0] = 0;
    for (int i = 1; i < 256; i++)
        index[i] = index[i - 1] + counter[i - 1];
    for (int i = 0; i < n; i++)
        b[index[get_byte(a[i])]++] = a[i];
}

void RadixSort()
{
    for (int i = 0; i < sizeof(int); i++)
        CountSort(v[i % 2], v[!(i % 2)], i);
}

int main()
{
    f>>n>>a>>b>>c;
    v[0][0] = b % c;
    for (int i = 1; i < n; i++)
        v[0][i] = (1LL * a * v[0][i - 1] % c + b) % c;
    RadixSort();
    for (int i = 0; i < n; i += 10)
        g<<v[0][i]<<' ';
    return 0;
}