Cod sursa(job #2541559)

Utilizator BlueLuca888Girbovan Robert Luca BlueLuca888 Data 8 februarie 2020 16:16:26
Problema Radix Sort Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.91 kb
#include <iostream>
#include <fstream>
#define MOD 256
#define SIZE 10000005

using namespace std;

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

int n, a, b, c;
int maxx, cif;
int z;
int v[SIZE], w[SIZE], f[MOD];

int main (){
     fin>>n>>a>>b>>c;
     v[1]=b;
     maxx=b;
     for(int i=2; i<=n; i++){
          v[i]=(v[i-1]*1LL*a + b)%c;
          if(v[i] > maxx)
               maxx=v[i];
     }

     while(maxx != 0){
          cif++;
          maxx/=MOD;
     }

     for(int c=1; c<=cif; c++){

          for(int i=0; i<MOD; i++) f[i]=0;

          for(int i=1; i<=n ; i++) f[((v[i] >> z)&255)]++;

          for(int i=1; i<MOD; i++) f[i]+=f[i-1];

          for(int i=n; i>=1 ; i--) w[f[((v[i]>>z)&255)]--]=v[i];

          for(int i=1; i<=n ; i++) v[i]=w[i];

          z+=8;
     }

     for(int i=1; i<=n; i+=10) fout<<v[i]<<" ";
     return 0;
}