Cod sursa(job #2134487)

Utilizator flaviu_2001Craciun Ioan-Flaviu flaviu_2001 Data 17 februarie 2018 23:45:36
Problema Radix Sort Scor 30
Compilator cpp Status done
Runda Arhiva educationala Marime 0.93 kb
#include <bits/stdc++.h>

using namespace std;

const int64_t base = 256;
int n, v[10000005], r[10000005];

void counting_sort(int a[], int b[], int64_t byte)
{
    int64_t cnt[260] = {0}, index[260] = {0};
    for(int64_t i = 0; i < n; ++i){
        int64_t dig = (a[i]>>(byte*8))&255;
        ++cnt[dig];
    }
    for (int64_t i = 1; i < 256; ++i)
        index[i] = index[i-1]+cnt[i-1];
    for (int64_t i = 0; i < n; ++i){
        int64_t dig = (a[i]>>(byte*8))&255;
        b[index[dig]++] = a[i];
    }
}

int main()
{
    ifstream fin ("radixsort.in");
    ofstream fout ("radixsort.out");
    fin >> n;
    int64_t a, b, c;
    fin >> a >> b >> c;
    v[0] = b;
    for (int64_t i = 1; i < n; ++i)
        v[i] = (1LL*a*v[i-1]+b)%c;
    for (int64_t i = 0; i < 4; ++i)
        if(i%2==0)
            counting_sort(v, r, i);
        else counting_sort(r, v, i);
    for (int64_t i = 0; i < n; i += 10)
        fout << r[i] << " ";
    return 0;
}