Cod sursa(job #3175777)

Utilizator SimifilLavrente Simion Simifil Data 26 noiembrie 2023 13:29:02
Problema Radix Sort Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.69 kb
#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>
#include <fstream>
using namespace std;
int N, a, b, c, cur, l = 0, l2 = 0;
#define MAX_N 10000001
#define MAX_BITS 31
#define BITS_PER_STEP 8

const int BASE = (1 << BITS_PER_STEP);
const int MASK = BASE - 1;

int v[MAX_N];
int v2[MAX_N];

int v_aux[MAX_N];
int freq[BASE];
int ind[BASE];

//vector <long long> v;
//vector <long long> v2;
ifstream f ("radixsort.in");
ofstream g ("radixsort.out");


int Sort( int v[], int aux[], int n, int bits )
{
    if( bits >= MAX_BITS )
        return 0;

    int i;

    for( i = 0; i < n; ++i )
        freq[i] = 0;
    //memset(freq, 0, sizeof(freq));

    for( i = 0; i < n; ++i )
    {
        ++freq[ v[i] >> bits & MASK ];
    }

    ind[0] = 0;
    for( i = 1; i < BASE; ++i )
    {
        ind[i] = ind[i-1] + freq[i - 1];
    }
    for( i = 0; i < n; ++i )
    {
        ind[ v[i] >> bits & MASK ]++;
        aux[ ind[ v[i] >> bits & MASK ] ] = v[i];
    }
    Sort( v, aux, n, bits + BITS_PER_STEP );
    return 0;
}

int main()
{
    ios_base::sync_with_stdio(false);
    f.tie(NULL); g.tie(NULL);

    f >> N >> a >> b >> c;
    v[0] = b;
    cur = b;
    for( int i = 1; i < N; ++i )
    {
        cur = (a * cur + b) % c;
        v[i] = cur;
        //if( (i - 1) % 10 == 0 )
        //{
        //    ++l;
        //}
    }
    Sort( v, v_aux, N, 0 );
    int st = 0;
    while( st < N )
    {
        g << v[st] << " ";
        if( st % 10 == 0 )
            v2[l2] = v[st], ++l2;
        ++st;
    }
    st = 0;
    while( st < l2 )
    {
        //g << v2[st] << " ";
        ++st;
    }
    return 0;
}