Cod sursa(job #2898405)

Utilizator madalin1902Florea Madalin Alexandru madalin1902 Data 6 mai 2022 17:36:49
Problema Radix Sort Scor 30
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.13 kb
#include <bits/stdc++.h>
using namespace std;


int N, A, B, C, v[10000002], aux[10000002];
int freq[261], poz[261];


int main() {
    ifstream fin("radixsort.in");
    fin >> N >> A >> B >> C;
    fin.close();

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

    for(int i = 0, mask = 255; i < 32; i += 8, mask <<= 8) {
        for(int j = 1; j <= N; j++) {
            int cifra = (v[j] & mask) >> i;
            freq[cifra]++;
        }

        for(int j = 1; j < 256; j++)
            freq[j] += freq[j - 1];

        for(int j = 1; j <= N; j++) {
            int cifra = (v[j] & mask) >> i;
            poz[cifra]++;
            int newpoz = poz[cifra];
            if(cifra > 0) newpoz += freq[cifra - 1];
            aux[newpoz] = v[j];
        }

        for(int j = 1; j <= N; j++)
            v[j] = aux[j];

        for(int j = 0; j < 256; j++) {
            freq[j] = 0;
            poz[j] = 0;
        }
    }

    ofstream fout("radixsort.out");
    for(int i = 1; i <= N; i += 10)
        fout << v[i] << ' ';
    fout.close();
}