Cod sursa(job #2532046)

Utilizator victorzarzuZarzu Victor victorzarzu Data 27 ianuarie 2020 10:33:22
Problema Radix Sort Scor 30
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.69 kb
#include <bits/stdc++.h>
using namespace std;
ofstream g("radixsort.out");
int n,a,b,c;
int p = 31999;
char buffer[32010];
unsigned int maxim = -INFINITY;

vector<unsigned int> v;

void inc()
{
    ++p;
    if(p == 32000)
    {
        fread(buffer,1,32000,stdin);
        p = 0;
    }
}

void read(int &x)
{
    x = 0;
    while(buffer[p] < '0' || buffer[p] > '9')
        inc();
    while(buffer[p] >= '0' && buffer[p] <= '9')
    {
        x = x * 10 + buffer[p] - '0';
        inc();
    }
}

void Read()
{
    freopen("radixsort.in","r",stdin);
    read(n);
    read(a);
    read(b);
    read(c);
}

void Solve()
{
    int last = b,current;
    v.push_back(b);
    for(int i = 2;i <= n;++i)
    {
        current = (a * last + b) % c;
        v.push_back(current);
        if(current > maxim)
            maxim = current;
        last = current;
    }
}

void countSort(vector<unsigned int>& v,int exp)
{
    unsigned int count[10] = {0};
    unsigned int output[v.size()];

    for(int i = 0;i < v.size();++i)
        count[(v[i] / exp) % 10]++;

    for(int i = 1;i < 10;++i)
        count[i] += count[i - 1];

    for(int i = v.size() - 1; i >= 0;--i)
    {
        output[count[(v[i] / exp) % 10] - 1] = v[i];
        count[(v[i] / exp) % 10] --;
    }

    for(int i = 0;i < v.size();++i)
        v[i] = output[i];
}

void RadixSort(vector<unsigned int>& v)
{
    for(int exp = 1; maxim / exp > 0; exp *= 10)
        countSort(v,exp);
}

void Print()
{
    for(int i = 0; i < v.size() - 1;i += 10)
        g<<v[i]<<" ";
    g.close();
}

int main()
{
    Read();
    Solve();
    RadixSort(v);
    Print();
    return 0;
}