Cod sursa(job #2458948)

Utilizator hurjui12AlexandruHurjui Alexandru-Mihai hurjui12Alexandru Data 21 septembrie 2019 22:36:36
Problema Radix Sort Scor 30
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.83 kb
#include <cstdio>
#include <fstream>
#include <cstring>
#include <cmath>
using namespace std;

ifstream fin("radixsort.in");
FILE *fout = fopen("radixsort.out", "w");

#define bsize 1<<20
char buff[bsize];
char stiva[10];
int poz = bsize;

/*
inline char ch()
{
    if (poz == bsize)
    {
        fread(buff, 1, bsize, fin);
        poz = 0;
    }
    return buff[poz++];
}

inline int nr()
{
    char x;
    do
    {
        x = ch();
    } while (isdigit(x) == 0);
    int k = 0;
    while (isdigit(x))
    {
        k = k*10 + x-48;
        x = ch();
    }
    return k;
}
*/
inline void scrie(char x)
{
    if (poz == bsize)
    {
        fwrite(buff, 1, bsize, fout);
        poz = 0;
    }
    buff[poz++] = x;
}

inline void scrieint(int x)
{
    do
    {
        stiva[0]++;
        stiva[stiva[0]] = x%10 + 48;
        x = x/10;
    } while (x!=0);
    while (stiva[0] > 0)
    {
        scrie(stiva[stiva[0]]);
        stiva[0]--;
    }
}

void gol()
{
    fwrite(buff, 1, poz, fout);
}

int a[10000001][2], N;
bool v;

void cifsort(int poz)
{
    int p = 1, i, b[10] = {}, c;
    for (i = 1; i<=poz; i++)
        p = p*10;
    for (i = 1; i<=N; i++)
    {
        c = a[i][v]/p%10;
        b[c]++;
    }
    for (i = 1; i<10; i++)
        b[i] = b[i-1] + b[i];
    for (i = N; i>=1; i--)
    {
        c = a[i][v]/p%10;
        a[b[c]][1-v] = a[i][v];
        b[c]--;
    }
    v = 1-v;
}

int main()
{
    int i, maxc = 0, cif;
    int A, B, C;
    fin >> N >> A >> B >> C;
    a[1][0] = B;
    for (i = 2; i<=N; i++)
    {
        a[i][0] = (A*a[i-1][0]+B)%C;
        cif = log10(a[i][0])+1;
        if (cif > maxc)
            maxc = cif;
    }
    for (i = 0; i<maxc; i++)
        cifsort(i);
    poz = 0;
    for (i = 1; i<=N; i=i+10)
    {
        scrieint(a[i][v]);
        scrie(' ');
        //fprintf(fout, "%i ", a[i][v]);
    }
    gol();
    return 0;
}