Cod sursa(job #1714608)

Utilizator oldatlantianSerban Cercelescu oldatlantian Data 8 iunie 2016 20:33:26
Problema Radix Sort Scor 30
Compilator cpp Status done
Runda Arhiva educationala Marime 1.2 kb
#define  MAGIC 0 ///Tab-ul de 2 ma ameteste...
#include <bits/stdc++.h>
using namespace std;
typedef long long i64;

const int NMAX = 10000005;
const int BYTE = 256;

int n;
i64        v[NMAX];
queue<i64> q[BYTE];

inline int mask(i64 arg, int step) {
  return (arg & ((BYTE-1LL)<<--step*8))>>step*8;
}

void rsort(void) {
  int buff, tmp, f[BYTE];

  buff = 1;
  memset(f, 0x00, sizeof(f));

  for(int i=1; i<=n; ++i)
    q[mask(v[i], 1)].push(v[i]);
  for(int i=1; i<=4; ++i) {
    for(int j=0; j<BYTE; ++j)
      f[j] = q[j].size();
    for(int j=0; j<BYTE; ++j) {
      while(f[j]--) {
        tmp = q[j].front();
        q[mask(tmp, i)].push(tmp);
        q[j].pop();
      }
    }
  }
  for(int i=0; i<BYTE; ++i)
    while(!q[i].empty())
      v[buff++] = q[i].front(),
      q[i].pop();
}

int main(void) {
  FILE *fi = fopen("radixsort.in", "r");
  FILE *fo = fopen("radixsort.out", "w");
  i64 a, b, c;

  fscanf(fi,"%d %lld %lld %lld",&n,&a,&b,&c);

  v[1] = b;
  for(int i=2; i<=n; ++i)
    v[i] = (a * v[i-1] + b) % c;

  rsort();

  for(int i=1; i<=n; i+=10)
    fprintf(fo,"%lld ",v[i]);
  fprintf(fo,"\n");

  fclose(fi);
  fclose(fo);
  return MAGIC;
}