Cod sursa(job #1335518)

Utilizator karlaKarla Maria karla Data 5 februarie 2015 17:21:16
Problema Radix Sort Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.34 kb
#include <stdio.h>
FILE*f=fopen("radixsort.in","r"),*g=fopen("radixsort.out","w");

# define NR 10000010
#define biti 8

long n,v[NR],ord[NR];
long b,a,c;


using namespace std;

void citire()
{
    fscanf(f,"%ld %ld %ld %ld",&n,&a,&b,&c);
}


void generare()
{
    v[1]=b;
    for(long i=2;i<=n;i++)
    {
       v[i] = (1LL * a * v[i-1] + b) % c;
    }
}

int cifra(int x, long long p)
{
    return (x << p) & 255;
}

void ordonare()
{
    long s[257];
    long long p = 0;
        for(long j = 1; j <= 4; j++)
        {
            for (long i = 0; i <= 256; i++)
                s[i] = 0;
            // fregvente cifre
            for (long i = 1;i <= n; i++)
                s[  cifra(v[i], p) ]++;
            // sume partiale
            for (long i = 1; i < 255 ;i++)
                s[i] += s[i-1];
            // ordonare
            for (long i = n; i >= 1; i--) {
                ord[ s[ cifra(v[i], p) ] ] = v[i];
                s[  cifra(v[i], p) ] --;
            }
            // copiere
            for (long i = 1; i <= n; i++)
                v[i] = ord[i];
            p += 8;
        }
}

void afisare()
{
    for(long i=1;i<=n;i+=10)
    {
            fprintf(g,"%ld ",v[i]);
    }
}

int main()
{
    citire();
    generare();
    ordonare();
    afisare();
    return 0;
}