Cod sursa(job #1438713)

Utilizator S7012MYPetru Trimbitas S7012MY Data 20 mai 2015 17:57:09
Problema Radix Sort Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.68 kb
#include <iostream>
#include <fstream>
#define DN 10000005
#define MSK 1023
using namespace std;

int n,a,b,c,v[DN],vx[DN],cnt[MSK+2];

int main() {
  ifstream f("radixsort.in");
  ofstream g("radixsort.out");
  f>>n>>a>>b>>c;
  v[0]=b;
  for(int i=1; i<n; ++i) v[i]=(v[i-1]*a+b)%c;

  for(int sh=0; sh<=31; sh+=10) {
    for(int i=0; i<n; ++i) {
      int cc=(v[i]>>sh)&MSK;
      ++cnt[cc+1];
    }
    for(int i=1; i<=MSK; ++i) cnt[i]+=cnt[i-1];
    for(int i=0; i<n; ++i) {
      int cc=(v[i]>>sh)&MSK;
      //cout<<cc<<' '<<cnt[cc]<<'\n';
      vx[cnt[cc]]=v[i];
      ++cnt[cc];
    }
    memcpy(v,vx,sizeof(vx));
    memset(cnt,0,sizeof(cnt));
  }
  for(int i=0; i<n; i+=10) cout<<v[i]<<' ';
}