Cod sursa(job #2642509)

Utilizator LivcristiTerebes Liviu Livcristi Data 15 august 2020 18:58:10
Problema Radix Sort Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.13 kb

#include <stdio.h>
#define NMAX 10000005

using namespace std;

FILE* fin, * fout;
unsigned int n, v[NMAX];
unsigned int tmp[NMAX];

void sortByDigit(unsigned int p) {
    unsigned int count[256] = { 0 };
    for (unsigned int i = 1;i <= n;++i) {
        unsigned int nr = (v[i] >> p) % 256;
        ++count[nr];
    }
    for (unsigned int i = 1;i < 256;++i)
        count[i] += count[i - 1];
    for (unsigned int i = n;i > 0;--i) {
        unsigned int nr = (v[i] >> p) % 256;
        tmp[count[nr]--] = v[i];
    }
    for (unsigned int i = 1;i <= n;++i)
        v[i] = tmp[i];
}

void radixSort() {
    unsigned int p = 0;
    for (int i = 1;i <= 4;++i) {
        sortByDigit(p);
        p += 8;
    }
}

int main()
{
    fin = fopen("radixsort.in", "r");
    fout = fopen("radixsort.out", "w");

    unsigned int a, b, c;
    fscanf(fin, "%i %i %i %i", &n, &a, &b, &c);
    v[1] = b;
    for (unsigned int i = 2;i <= n;++i) {
        v[i] = ((long long int)a * v[i - 1] + b) % c;
    }
    radixSort();
    for (unsigned int i = 1;i <= n;i += 10)
        fprintf(fout,"%i ", v[i]);


    return 0;
}