Cod sursa(job #1935287)

Utilizator NuamcontJohn George Nuamcont Data 22 martie 2017 10:16:26
Problema Radix Sort Scor 30
Compilator cpp Status done
Runda Arhiva educationala Marime 0.94 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <cmath>
using namespace std;
ifstream fin("radixsort.in");
ofstream fout("radixsort.out");
vector <int> v;
vector <int> v2, fr;
int n, a, b, c;
int radix(int k) {
    fr.resize(10, 0);
    int ok = 0;
    int p = pow(10, k);
    for(int i = 0; i < n; i++) {
        fr[v[i]/p %10]++;
        ok += v[i]/(p*10);
    }
    for(int i = 1; i<= 9;  i++) {
        fr[i] +=fr[i-1];
    }
    for(int i = n - 1; i >= 0; i--) {
        fr[v[i]/p %10]--;
        v2[fr[v[i]/p %10]] = v[i];
    }
    fr.clear();
    v.swap(v2);
    return ok;
}
int main()
{
    fin>>n>>a>>b>>c;
    v.push_back(b);
    int aux = b%c;
    for(int i = 1; i < n; i++) {
        aux = (aux * a)%c;
        v.push_back((aux + v[i-1])%c);
    }
    v2.resize(n);
    int k = 0;
    while(radix(k++));
    for(int i = 0; i < n; i+=10) {
        fout<<v[i]<<' ';
    }
    return 0;
}