Cod sursa(job #2527875)

Utilizator stefanpiturStefan Alexandru Pitur stefanpitur Data 20 ianuarie 2020 22:49:27
Problema Radix Sort Scor 30
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.22 kb
#include <iostream>
#include <cstdio>
using namespace std;
const int nmax = 10000000;
int v[nmax+1],new_v[nmax+1];

void copy_new_v(int n){
    for(int i=1; i<=n; i++)
        v[i] = new_v[i];
}

int power(int digit){
    int ans = 1;
    while(digit--)
        ans *= 10;
    return ans;
}

void counting_sort(int digit, int n){
    int cif[10];
    int p10 = power(digit);
    int i;
    for(i=0; i<10; i++)
        cif[i] = 0;
    for(i=1; i<=n; i++)
        cif[v[i]/p10%10]++;
    for(i=1; i<10; i++)
        cif[i] += cif[i-1];
    for(i=9; i>0; i--)
        cif[i] = cif[i-1];
    cif[0] = 0;
    for(i=1; i<=n; i++)
        new_v[++cif[v[i]/p10%10]] = v[i];
    copy_new_v(n);
}

int main()
{
    FILE *fin, *fout;
    int n,a,b,c,i,maxim,cif;
    fin = fopen("radixsort.in","r");
    fout = fopen("radixsort.out","w");
    fscanf(fin,"%d %d %d %d",&n,&a,&b,&c);
    v[1] = maxim = b;
    for(i=2; i<=n; i++){
        v[i] = (1LL*a*v[i-1] + 1LL*b)%c;
        maxim = maxim > v[i] ? maxim : v[i];
    }
    cif = 0;
    while(maxim){
        cif++;
        maxim /= 10;
    }
    for(i=0; i<cif; i++)
        counting_sort(i, n);
    for(i=1; i<=n; i+=10)
        fprintf(fout,"%d ",v[i]);
    fclose(fin);
    fclose(fout);
    return 0;
}