Cod sursa(job #2679814)

Utilizator teodorescunicolasteodorescu nicolas alexandru teodorescunicolas Data 1 decembrie 2020 16:58:57
Problema Radix Sort Scor 30
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.2 kb
#include <stdio.h>
#include <string.h>
#define NMAXX 10000000
#define MAXBIT 32
#define STEP 8
#define PUTMAXX 256

using namespace std;

int n, v[2][NMAXX], frecv[PUTMAXX], poz[PUTMAXX];
void sort( int p, int nrbiti ) {
    int i, aux;
    if ( nrbiti == MAXBIT )
        return;
    memset( frecv, 0, sizeof(frecv) );
    for ( i = 0; i < n; i++ ) {
        aux = v[p][i] >> nrbiti & (PUTMAXX - 1);
        frecv[aux]++;
    }
    poz[0] = 0;
    for ( i = 1; i < PUTMAXX; i++ ) {
        poz[i] = poz[i - 1] + frecv[i - 1];
    }
    for ( i = 0; i < n; i++ ) {
        aux = v[p][i] >> nrbiti & (PUTMAXX - 1);
        v[(p + 1) % 2][poz[aux]] = v[p][i];
        poz[aux]++;
    }
    sort( (p + 1) % 2, nrbiti + STEP );
}

int main()
{
    FILE *fin, *fout;
    int a, b, c, i;
    fin = fopen( "radixsort.in", "r" );
    fout = fopen( "radixsort.out", "w" );
    fscanf( fin, "%d%d%d%d", &n, &a, &b, &c );
    v[0][0] = b;
    for ( i = 1; i < n; i++ ) {
        v[0][i] = (long long)(a * v[0][i - 1] + b) % c;
    }
    sort( 0, 0 );
    for ( i = 0; i < n; i += 10 ) {
        fprintf( fout, "%d ", v[0][i] );
    }
    fclose( fin );
    fclose( fout );
    return 0;
}