Cod sursa(job #1842168)

Utilizator bt.panteaPantea Beniamin bt.pantea Data 6 ianuarie 2017 16:45:13
Problema Radix Sort Scor 30
Compilator cpp Status done
Runda Arhiva educationala Marime 1.17 kb
#include <iostream>
#include <fstream>
#define NMAX 10000010
#define GetBit(x) (x & 1<<byte) != 0 ? 1 : 0
using namespace std;
ifstream f ("radixsort.in");
ofstream g ("radixsort.out");

int v[2][NMAX], n, a, b, c;
int sw = 0;
void Write(int a[])
{
    for (int i = 0; i < n; i++)
        cout<<a[i]<<' ';
    cout<<'\n';
}

void CountSort(int a[], int b[], int byte)
{
    //Write(a);
    int index0 = 0, index1 = 0;
    for (int i = 0; i < n; i++)
    {
        if (a[i] & 1<<byte)
            continue;
        else index1++;
    }
    for (int i = 0; i < n; i++)
        if (a[i] & 1<<byte)
            b[index1++] = a[i];
        else
            b[index0++] = a[i];
    //Write(b);

    //cout<<'\n';
}

void RadixSort()
{
    int bit = 0, bitmax = sizeof(v[0][0]) * 8;
    while (bit < bitmax)
    {
        CountSort(v[bit % 2], v [!(bit % 2)], bit);
        bit++;
    }
}

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