Cod sursa(job #2717013)

Utilizator MateGMGozner Mate MateGM Data 6 martie 2021 09:15:28
Problema Radix Sort Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.4 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <cstring>
#include <cstdio>
using namespace std;


void count_sort(int v[],int n,int word,int ki[])
{
    int count[1<<16];
    int index[1<<16];
    memset(count,0,sizeof(count));

    for(int i=0;i<n;i++)
    {
        count[((v[i])>>(word*16))&0xffff]++;
    }
    index[0]=0;

    for (int i = 1; i < (1<<16); i++)
        index[i]=index[i-1]+count[i-1];

    for(int i=0;i<n;i++){
         ki[index[((v[i])>>(word*16))&0xffff]++]=v[i];
    }

}

void radix_sort(int v[],int n)
{

    int *temp=new int[n];
    count_sort(v,n,0,temp);
    count_sort(temp,n,1,v);
    delete[]temp;
}

int main()
{
    ifstream be("radixsort.in");
    freopen("radixsort.out","w",stdout);
    int n,a,b,c;
    be>>n>>a>>b>>c;
    int v[n];
    v[0] = b % c;
    for(int i = 1; i < n; i ++)
        v[i] = (1LL * a * v[i-1] % c + b) % c;
    radix_sort(v,n);
    char *output=new char[(n/10+1)*11+4];
    int idx=0;
    char current[11];
    for(int i=0;i<n;i+=10)
    {
        int szam=v[i];
        int k=0;
        while(szam)
        {
            current[k++]=szam%10+'0';
            szam/=10;
        }
        for(int j=k-1;j>=0;j--)
        {
            output[idx++]=current[j];
        }
        output[idx++]=' ';
    }
    output[idx++]='\0';
    puts(output);
    delete[] output;

    return 0;
}