Cod sursa(job #2817859)

Utilizator ElizaTElla Rose ElizaT Data 14 decembrie 2021 13:07:45
Problema Radix Sort Scor 70
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.2 kb
#include <bits/stdc++.h>
#define MAX_N 10000000 + 1
#define RADIX 0xFF
#define RADIX_SIZE 8

using namespace std;

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

int n;
int v[MAX_N];
#define TOTAL_BYTES sizeof(v[0])
#define bucket(x) ((x >> (byte * 8)) & RADIX)

void count_sort(int a[], int b[], int byte) {
    int cnt[1 << RADIX_SIZE];
    int cnt1[1 << RADIX_SIZE];
    memset(cnt, 0, sizeof(cnt));
    for(int i = 0;i < n;i++)
        cnt[bucket(a[i])]++;
    cnt1[0] = 0;
    for(int i = 1;i < 1 << RADIX_SIZE;i++)
        cnt1[i] = cnt1[i - 1] + cnt[i - 1];
    for(int i = 0;i < n;i++)
        b[cnt1[bucket(a[i])]++] = 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(ofstream& f) {
    for(int i = 0;i < n;i += 10)
        f << v[i]<< ' ';
}
int main()
{
    read();
    radix_sort();
    write(fout);
    return 0;
}