Cod sursa(job #2194248)

Utilizator andreiomd1Onut Andrei andreiomd1 Data 12 aprilie 2018 17:44:29
Problema Radix Sort Scor 30
Compilator cpp Status done
Runda Arhiva educationala Marime 1.27 kb
#include <bits/stdc++.h>

using namespace std;

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

long long lgput (int n, int p)
{
    long long sol=1;

    long long aux=n;

    int i;

    for(i=0; (1<<i)<=p; ++i) {
        if((p&(1<<i))!=0)
            sol*=aux;
        aux*=aux;
    }

    return sol;
}

long long n, a, b, c, aux, v, xx;
long long maxput=1;
int i, j, t;
int nc, Max=0;

vector <int> A, C[15];

int main()
{
    f>>n>>a>>b>>c;

    A.push_back(b);

    xx=A[0];
    nc=0;
    while(xx) {
        nc++;
        xx/=10;
    }
    if(nc>Max)
        Max=nc;

    for(i=1; i<n; i++) {
        v=(a*A[i-1]+b)%c;
        A.push_back(v);

        xx=A[i];
        nc=0;
        while(xx) {
            nc++;
            xx/=10;
        }
        if(nc>Max)
            Max=nc;

    }

    maxput=lgput(10, Max-1);

    for(long long  putere = 1; putere <= maxput; putere *= 10) {

        for(j=0; j<n; j++)
            C[A[j]/putere%10].push_back(A[j]);

        A.clear();

        for(j=0; j<=9; j++) {

            for(t=0; t<C[j].size(); t++)
                A.push_back(C[j][t]);

            C[j].clear();
        }

    }


    for(i=0; i<n; i+=10)
        g<<A[i]<<' ';

    return 0;
}