Cod sursa(job #1837976)

Utilizator BLz0rDospra Cristian BLz0r Data 30 decembrie 2016 18:42:07
Problema Radix Sort Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.5 kb
#include <fstream>
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

#define BUCKETS 256 // 1 bucket de 8 biti

ifstream fin("radixsort.in");
ofstream fout("radixsort.out");

void RadixSort(vector<int> &V){

    int Mask = BUCKETS - 1; // 255 = 1111 1111
    int N = V.size();

    vector<int> Cnt, Sol;
    Cnt.resize(BUCKETS);
    Sol.resize(V.size());

    // sortez pe bucati de 8 biti
    for (int i = 0; i < 32; i += 8) {
        fill(Cnt.begin(), Cnt.end(), 0); //folosesc count sort

        // adaug fiecare numar la codul corespunzator
        for (int j = 0; j < N; ++j)
            Cnt[(V[j] >> i) & Mask]++;

        // sume partiale pe vectorul de frecventa pentru a determina pozitiile elementelor in vector
        for (int j = 1; j < BUCKETS; ++j)
            Cnt[j] += Cnt[j-1];

        // iau numerele si le rearanjez
        for (int j = N-1; j >= 0; --j)
            Sol[--Cnt[(V[j] >> i) & Mask]] = V[j];

        // mut elementele in vectorul meu
        copy(Sol.begin(), Sol.end(), V.begin());
    }
}

int main(){

    vector<int> V;

    int N, A, B, C;

    // citire
    fin >> N >> A >> B >> C;

    V.resize(N);

    V[0] = B;

    // creez vectorul dupa formula data
    for (int i = 1; i < N; ++i)
        V[i] = (1LL * V[i - 1] * A + B) % C;

    // sortez vectorul prin metoda RadixSort
    RadixSort(V);

    // afisare
    for (int i = 0; i < N; i += 10)
        fout << V[i] << " ";

    return 0;
}