Cod sursa(job #2126016)

Utilizator TudorVersoiuVersoiu Tudor Sorin TudorVersoiu Data 8 februarie 2018 23:05:46
Problema Radix Sort Scor 30
Compilator cpp Status done
Runda Arhiva educationala Marime 1.17 kb
#include <iostream>
#include <fstream>
#include <vector>

using namespace std;
ifstream f("radixsort.in" );
ofstream g("radixsort.out");

int N;
int v[10000001];
vector<int> group[10];

void GenerateArray()
{
    int A, B, C;
    f >> N >> A >> B >> C;

    v[1] = B;
    for ( int i=2; i<=N; i++ )
        v[i] = (A * v[i-1] + B) % C;
}

int Cif(int x, int pos) {
    for ( int i=1; i<pos; i++ )
        x /= 10;
    return x%10;
}
int NrCif(int x)
{
    int ncif = 0;
    while ( x ) {
        x/=10;
        ncif++;
    }
    return ncif;
}

void RadixSort(int v[], int N)
{
    int passes = 1;

    for ( int i=1; i<=N; i++ )
        passes = max(passes, NrCif(v[i]));

    for ( int nPas=1; nPas<=passes; nPas++ )
    {
        for ( int i=1; i<=N; i++ )
            group[Cif(v[i], nPas)].push_back(v[i]);

        int k = 0;
        for ( int j=0; j<=9; j++ ) {
                for ( unsigned int i=0; i<group[j].size(); i++ )
                    v[++k] = group[j][i];
                group[j].erase(group[j].begin(), group[j].end());
            }

    }

}


int main()
{
    GenerateArray();
    RadixSort(v, N);

    for ( int i=0; i*10+1<=N; i++ )
        g << v[i*10+1] << ' ';
}