Cod sursa(job #3170233)

Utilizator MihaelaCismaruMihaela Cismaru MihaelaCismaru Data 16 noiembrie 2023 23:38:42
Problema Radix Sort Scor 30
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.23 kb
#include<fstream>
#include<vector>
using namespace std;
ifstream in ("radixsort.in");
ofstream out ("radixsort.out");
unsigned int N,A,B,C,maxim;
unsigned int v[10000005], aux[10000005];
unsigned int cnt[300];
pair<int,int> index[300];
int main (void) {
    in >> N >> A >> B >> C;
    v[1] = B;
    for (int i = 2; i <= N; i ++) {
        v[i] = (A * v[i-1] + B) % C;
    }

    for (int byt = 0; byt <= 3; byt ++) {
        for (int i = 0; i <= maxim; i ++) {
            cnt[i] = 0;
        }
        maxim = 0;
        for (int i = 1; i <= N; i ++) {
            unsigned int byte = (v[i] >> (8*byt)) & ((1<<8) - 1);
            cnt[byte] ++;
            maxim = max (maxim, byte);
            aux[i] = v[i];
        }
        index[0].first = 1;
        index[0].second = 1;
        for (int i = 1; i <= maxim; i ++) {
            index[i].first = index[i-1].first + cnt[i-1];
            index[i].second = index[i].first;
        }
        int n = 0;
        for (int i = 1; i <= N; i ++) {
            unsigned int byte = (aux[i] >> (8*byt)) & ((1<<8) - 1);
            v[index[byte].second++] = aux[i];
        }

    }
    for (int i = 1; i <= N; i += 10) {
        out << v[i] <<" ";
    }
    return 0;
}