Cod sursa(job #2043837)

Utilizator tziplea_stefanTiplea Stefan tziplea_stefan Data 20 octombrie 2017 17:06:44
Problema Radix Sort Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.24 kb
#include <fstream>
#include <vector>
#define MOD 256
#define VAL 10000005

using namespace std;

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

int N, i, j, k, v[VAL];
long long nr, A, B, C;
vector <int> cif[VAL];
vector <int> X[MOD], Y[MOD];

void CreateNr(int ind, int X)
{
    while (X!=0)
    {
        cif[ind].push_back(X % MOD);
        X/=MOD;
    }
    while (cif[ind].size()<4)
      cif[ind].push_back(0);
}

int main()
{
    fin >> N >> A >> B >> C;
    v[1]=B;
    CreateNr(1, v[1]);
    for (i=2; i<=N; i++)
    {
        nr=(1LL*A*v[i-1]+B) % C;
        v[i]=nr;
        CreateNr(i, v[i]);
    }
    for (i=1; i<=N; i++)
      X[cif[i][0]].push_back(i);
    for (i=1; i<4; i++)
    {
        for (j=0; j<MOD; j++)
          for (k=0; k<X[j].size(); k++)
            Y[cif[X[j][k]][i]].push_back(X[j][k]);
        for (j=0; j<MOD; j++)
        {
            X[j].clear();
            for (k=0; k<Y[j].size(); k++)
              X[j].push_back(Y[j][k]);
            Y[j].clear();
        }
    }
    A=0;
    for (j=0; j<MOD; j++)
    {
        for (k=0; k<X[j].size(); k++)
        {
            A++;
            if (A % 10==1)
              fout << v[X[j][k]] << " ";
        }
    }
    fin.close();
    fout.close();
    return 0;
}