Cod sursa(job #2278548)

Utilizator Lazar_LaurentiuLazar Laurentiu Lazar_Laurentiu Data 8 noiembrie 2018 10:42:27
Problema Radix Sort Scor 30
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.73 kb
#include <iostream>
#include <fstream>
#include <vector>
#define MAX 10000010
#define MOD 256

using namespace std;
typedef long long ll;

ll n,a,b,c;
int v[MAX];
vector<int> m[MOD];
void sorteaza(int sh){
  int sz=0;
  for(int i=1;i<=n;i++)
    m[((v[i]>>sh)&(MOD-1))].push_back(v[i]);
  for(int i=0;i<MOD;i++)
    while(m[i].size()){
      for(auto j:m[i])v[++sz]=j;
      m[i].clear();
    }
}

int main()
{
    ifstream f ("radixsort.in");
    ofstream g ("radixsort.out");
    f>>n>>a>>b>>c;
    v[1]=b;
    for(int i=2;i<=n;i++)
      v[i]=(a*v[i-1]+b)%c;
    for(int sh=0;sh<31;sh+=8)
      sorteaza(sh);
    for(int i=1;i<=n;i+=10)
      g<<v[i]<<" ";
    f.close ();
    g.close ();
    return 0;
}