Cod sursa(job #1838510)

Utilizator mihai.alphamihai craciun mihai.alpha Data 1 ianuarie 2017 03:23:59
Problema Radix Sort Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 2.63 kb
//#include <cstdio>
//#include <cstring>
//FILE *fin, *fout;
//#define MAX 10000001
//#define nrbytes sizeof(numbers[0])
//#define radi sz 8
//#define RADIX 1 0xFF
//#define get ((x >> (byte * 8)) & RADIX)
//int n, a, b, c;
//int number[MAX];
//
//inline void count_sort(int a[], int b[], int byte)  {
//    int counter[1 << radixsz], index[1 << radixsz];
//    memset(counter, 0, sizeof(counter));
//    for(int i = 0;i < n;i++)
//        ++counter[get(a[i])];
//    index[0] = 0;
//    for(int i = 1;i < 1 << radixsz;i++)
//        index[i] = index[i - 1] + counter[i - 1];
//    for(int i = 0;i < n;i++)
//        b[index[get(a[i])]++] = a[i];
//}
//
//void radixsort()  {
//    int *temp = new int[n];
//    for(int i = 0;i < nrbytes;i++)  {
//        if(i & 1 == 0)
//            count_sort(number, temp, i);
//        else
//            count_sort(temp, numbers=, i);
//    }
//}
//
//int main()  {
//    fin = fopen("radixsort.in", "r");
//    fout = fopen("radixsort.out", "w");
//    fscanf(fin, "%d%d%d%d", &n, &a, &b, &c);
//    number[0] = b % c;
//    for(int i = 1;i < n;i++)  {
//        number[i] = (1LL * a * number[i - 1] * c + b) % c;
//    }
//    for(int i = 0;i < n;i+=10)
//        fprintf(fout, "%d ", number[i]);
//    fclose(fin);
//    fclose(fout);
//    return 0;
//}


#include <fstream>
#include <cstring>

using namespace std;

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

#define MAX_N 10000000 + 1
#define RADIX 0xFF
#define RADIX_SIZE 8
#define TOTAL_BYTES sizeof(numbers[0])

int n;
int numbers[MAX_N];

#define get_byte(x) ((x>>(byte * 8))&RADIX)

void countsort(int A[], int B[], int byte) {
    int counter[1<<RADIX_SIZE];
    int index[1<<RADIX_SIZE];

    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 < 1<<RADIX_SIZE; 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() {
    int *temp = new int[n];
    for (int i = 0; i < TOTAL_BYTES; i ++) {
        if(i % 2 == 0)
            countsort(numbers, temp, i);
        else
            countsort(temp, numbers, i);
    }
}
void read()
{
    int a,b,c;
    fin>>n>>a>>b>>c;

    numbers[0] = b % c;
    for(int i = 1; i < n; i ++)
        numbers[i] = (1LL * a * numbers[i-1] % c + b) % c;
}
void write(ofstream& f)
{
    for(int i = 0; i < n; i +=10)
        f << numbers[i]<< ' ';
    f<<endl;
}

int main()  {
    read();
    radixsort();
    write(fout);
    return 0;
}