Cod sursa(job #2622763)

Utilizator miramaria27Stroie Mira miramaria27 Data 1 iunie 2020 19:30:48
Problema Radix Sort Scor 30
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.28 kb
#include <iostream>
#include <fstream>
#include <vector>
using namespace std;
ifstream in("radixsort.in");
ofstream out("radixsort.out");

void counting(vector<long long> &a,vector<long long> &result,long long times, long long ma, long long n)
{
    long long nr[10]= {0};
    for(long long i=0; i<n; i++)
    {
        int cifra=(a[i]/times)%10;
        nr[cifra]++;
    }
    for(long long i=1; i<10; i++)
        nr[i]+=nr[i-1];

    for(long long i=n-1; i>=0; i--)
    {
        int cifra=(a[i]/times)%10;
        result[nr[cifra]-1]=a[i];
        nr[cifra]--;
    }

}
void radixsort(vector<long long> &a, long long n)
{
    long long ma=-1;
    for(long long i=0; i<n; i++)
        if(ma<a[i])
            ma=a[i];
    long long times=1;
    vector<long long> b(n);
    int i=0;
    while(ma/times>0)
    {
        if(i%2==0)
            counting(a,b,times,ma,n);
        else
            counting(b,a,times,ma,n);
        times*=10;
        i++;
    }
    if((i-1)%2==0)
        a=b;

}
int main()
{
    long long N,A,B,C;
    in>>N>>A>>B>>C;
    vector<long long>a(N);
    a[0]=B;
    for(long long i=1; i<N; i++)
        a[i]=(A*a[i-1]+B)%C;
    radixsort(a,N);
    for(long long i=0; i<N; i+=10)
        out<<a[i]<<" ";
    return 0;
}