Cod sursa(job #1935297)

Utilizator NuamcontJohn George Nuamcont Data 22 martie 2017 10:34:00
Problema Radix Sort Scor 30
Compilator cpp Status done
Runda Arhiva educationala Marime 0.9 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;
void radix(int k) {
    fr.resize(256, 0);
    for(int i = 0; i < n; i++) {
        fr[v[i]>>(8*k) & 255]++;
    }
    for(int i = 1; i< 256;  i++) {
        fr[i] +=fr[i-1];
    }
    cout<<fr[255]<<' ';
    for(int i = n - 1; i >= 0; i--) {
        fr[v[i]>>(8*k) & 255]--;
        v2[fr[v[i]>>(8*k) & 255]] = v[i];
    }
    fr.clear();
    v.swap(v2);
}
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);
    for(int k=0;k<4;k++) radix(k);
    for(int i = 0; i < n; i+=10) {
        fout<<v[i]<<' ';
    }
    return 0;
}