Cod sursa(job #2817855)

Utilizator ElizaTElla Rose ElizaT Data 14 decembrie 2021 13:02:09
Problema Radix Sort Scor 70
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.29 kb
#include <fstream>
#include <string.h>

using namespace std;

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

const int NMAX = 1e7l,BUCKET = 0xFF,BYTES = 8;
int n;
int v[NMAX + 1];
const int TOTAL_BYTES = sizeof(v[0]);

int bucket(int x, int byte) {
    return ((x >> (byte << 3)) & BUCKET);
}
void count_sort(int a[], int b[], int byte) {
    int cnt[1 << BYTES];
    int cnt1[1 << BYTES];
    memset(cnt, 0, sizeof(cnt));
    for(int i = 0;i < n;i++)
        cnt[bucket(a[i], byte)]++;
    cnt1[0] = 0;
    for(int i = 1;i < 1 << BYTES;i++)
        cnt1[i] = cnt1[i - 1] + cnt[i - 1];
    for(int i = 0;i < n;i++)
        b[cnt1[bucket(a[i], byte)]++] = a[i];
}
void radix_sort() {
    int *aux = new int[n];
    for (int i = 0;i < TOTAL_BYTES;i++) {
        if(i % 2 == 0)
            count_sort(v, aux, i);
        else
            count_sort(aux, v, i);
    }
}
void read() {
    int a,b,c;
    fin >> n >> a >> b >> c;
    v[0] = b % c;
    for(int i = 1;i < n;i++)
        v[i] = (1LL * a * v[i - 1] % c + b) % c;
}
void write() {
    for(int i = 0;i < n;i += 10)
        fout << v[i]<< ' ';
}

int main()
{
    ios_base::sync_with_stdio(false);
    fin.tie(NULL);
    fout.tie(NULL);
    read();
    radix_sort();
    write();
    return 0;
}