Cod sursa(job #2225889)

Utilizator CristianSoareSoare Cristian Costantin CristianSoare Data 28 iulie 2018 15:44:57
Problema Radix Sort Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.37 kb
#include <bits/stdc++.h>

using namespace std;

int v[10000001];
int orderedArray[10000001];
int countingSort [1 << 16];

void sortBucket (int v[], int n, int bucketSize, int whichBucket) {
    int mask = ((1 << bucketSize) - 1);
    int constant = 1 << bucketSize;
    for (int i = 0; i < constant; ++i) {
        countingSort[i] = 0;
    }

    for (int i = 1; i <= n; ++i) {
        int currentPosition = (v[i] >> (whichBucket * bucketSize)) & mask;
        countingSort[currentPosition] += 1;
    }

    for (int i = 1; i < constant; ++i) {
        countingSort[i] += countingSort[i - 1];
    }

    for (int i = n; i >= 1; --i) {
        int currentPosition = (v[i] >> (whichBucket * bucketSize)) & mask;
        orderedArray[countingSort[currentPosition]] = v[i];
        countingSort[currentPosition] -= 1;
    }

    for (int i = 1; i <= n; ++i) {
        v[i] = orderedArray[i];
    }
}

int main() {
    ifstream fin ("radixsort.in");
    ofstream fout ("radixsort.out");
    int n, a, b, c;
    fin >> n >> a >> b >> c;
    v[1] = b;
    for (int i = 2; i <= n; ++i) {
        int newValue = static_cast<int>((1LL * a * v[i - 1] + b) % c);
        v[i] = newValue;
    }

    for (int i = 0; i < 2; ++i) {
        sortBucket(v, n, 16, i);
    }

    for (int i = 1; i <= n; i += 10) {
        fout << v[i] << ' ';
    }
    return 0;
}