Cod sursa(job #1468836)

Utilizator mihaiadelinamihai adelina mihaiadelina Data 7 august 2015 01:17:29
Problema Radix Sort Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.84 kb
#include <fstream>
#include <vector>
using namespace std;

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

int a[10000001], N;

void radixSort (int byteNo) {
    int i, r, k, l;
    vector <int> bucket[256];

    //Initialize bucket count;
    for (i = 0; i < N; i++) {
        r = (a[i] >> (byteNo * 8) & 255);
        bucket[r].push_back(a[i]);
    }

    // colectam elementele din bucket
    for (k = 0, i = 0; k < 256; k++) {
        for (l = 0; l < bucket[k].size(); l++)
            a[i++] = bucket[k][l];
    }
}

int main() {
    int i;
    long long A, B, C;
    fin >> N >> A >> B >> C;

    a[0] = B;
    for (i = 1; i < N; i++) {
        a[i] = (int) ((A * a[i - 1] + B) % C);
    }

    for (i = 0; i < 4; i++) {
        radixSort(i);
    }

    for (i = 0; i < N; i += 10) {
        fout << a[i] << " ";
    }

    return 0;
}