Cod sursa(job #2451357)

Utilizator uvIanisUrsu Ianis Vlad uvIanis Data 26 august 2019 15:58:06
Problema Radix Sort Scor 70
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.95 kb
#include <bits/stdc++.h>
using namespace std;
int N, A, B, C, v[10000001], aux[10000001], counter[256];

void read()
{
    ifstream fin("radixsort.in");
    fin >> N >> A >> B >> C;
    v[0] = B % C;

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

void print()
{
    ofstream fout("radixsort.out");

    for(int i = 0; i < N; i += 10) fout << v[i] << ' ';
}

inline int getByte(int byte, int x){
    return (x >> (byte * 8)) & 255;
}

void countSort(int byte)
{
    for(int i = 1; i <= 255; i++) counter[i] = 0;

    for(int i = 0; i < N; i++)  counter[getByte(byte, v[i])] ++;

    for(int i = 1; i <= 255; i++) counter[i] += counter[i - 1];

    for(int i = N - 1; i >= 0; i--) aux[--counter[getByte(byte, v[i])]] = v[i];

    for(int i = 0; i < N; i++) v[i] = aux[i];

}

int main()
{
    read();

    for(int i = 0; i <= 3; i++)
    {
        countSort(i);
    }

    print();
}