Cod sursa(job #2044140)

Utilizator tziplea_stefanTiplea Stefan tziplea_stefan Data 20 octombrie 2017 22:30:50
Problema Radix Sort Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.98 kb
#include <fstream>
#include <vector>
#include <cstring>
#define MOD 256
#define VAL 10000005

using namespace std;

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

int N, M, i, j;
int v[VAL], byte;
int x[VAL];
long long A, B, C;

void Radix_Sort(int a[], int b[])
{
    int X[MOD], nr[MOD];
    int d, c, i, cif;
    memset(X, 0, sizeof X);
    for (i=1; i<=N; i++)
    {
        c=a[i] >> (byte*8) & (MOD-1);
        X[c]++;
    }
    nr[0]=1;
    for (cif=1; cif<MOD; cif++)
      nr[cif]=nr[cif-1]+X[cif-1];
    for (i=1; i<=N; i++)
    {
        c=a[i] >> (byte*8) & (MOD-1);
        d=nr[c]++;
        b[d]=a[i];
    }
}

int main()
{
    fin >> N >> A >> B >> C;
    v[1]=B;
    for (i=2; i<=N; i++)
      v[i]=(1LL*A*v[i-1]+B) % C;
    for (byte=0; byte<=3; byte++)
    {
        if (byte % 2==0)
          Radix_Sort(v, x);
        else
          Radix_Sort(x, v);
    }
    for (i=1; i<=N; i+=10)
      fout << v[i] << " ";
    fin.close();
    fout.close();
    return 0;
}