Cod sursa(job #2553558)

Utilizator AndreiD31Dragan Andrei AndreiD31 Data 22 februarie 2020 09:44:43
Problema Radix Sort Scor 30
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.33 kb
#include <bits/stdc++.h>

using namespace std;

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

vector <long long> v[11],new_v[11];
long long n,p,poz,number,j,copie,maxi,X,ant_X,A,B,C,i,nr;

int main()
{
    f>>n>>A>>B>>C;

    X=B;
    nr=0;copie=X;
    while(copie)
    {
        nr++;
        copie/=10;
    }
    maxi=max(maxi,nr);
    v[X%10].push_back(X);
    ant_X=X;

    for(i=2;i<=n;i++)
    {
        X=(A*ant_X+B)%C;
        nr=0;copie=X;
        while(copie)
        {
            nr++;
            copie/=10;
        }

        maxi=max(maxi,nr);
        v[X%10].push_back(X);

        ant_X=X;
    }

    p=10;
    for(poz=2;poz<=maxi;poz++)
    {
        for(i=0;i<=9;i++)
        {
            while(!v[i].empty())
            {
                number=v[i].back();
                new_v[number/p%10].push_back(number);
                v[i].pop_back();
            }
        }

        for(i=0;i<=9;i++)
        {
            while(!new_v[i].empty())
            {
                v[i].push_back(new_v[i].back());
                new_v[i].pop_back();
            }
        }

        p=p*10;
    }

    nr=0;
    for(i=0;i<=9;i++)
    while(!v[i].empty())
    {
        nr++;
        if(nr%10==1)g<<v[i].back()<<" ";
        v[i].pop_back();
    }
    return 0;
}