Cod sursa(job #1094959)

Utilizator danny794Dan Danaila danny794 Data 30 ianuarie 2014 02:48:33
Problema Radix Sort Scor 30
Compilator cpp Status done
Runda Arhiva educationala Marime 0.98 kb
#include <cstdio>
#include <queue>

using namespace std;

#define MOD 0xff

int N, A, B, C;
queue<int> bucket[2][256];
int swc;

void read() {
  freopen("radixsort.in", "r", stdin);
  freopen("radixsort.out", "w", stdout);
  scanf("%i%i%i%i", &N, &A, &B, &C);
  int prev = B, x;
  bucket[swc][prev & MOD].push(prev);
  for(int i = 1; i < N; i++) {
    x = (A * prev + B) % C;
    bucket[swc][x & MOD].push(x);
    prev = x;
  }
}

void solve() {
  for(int i = 1; i < 4; i++) {
    for(int j = 0; j < 256; j++)
      while(!bucket[swc][j].empty()) {
        int x = bucket[swc][j].front();
        bucket[swc][j].pop();
        bucket[1 - swc][(x >> (8 * i)) & MOD].push(x);
      }
    swc = 1 - swc;
  }
}

void printSolution() {
  int k = 1;
  for(int i = 0; i < 256; i++) {
    while( !bucket[swc][i].empty() ) {
      if( k % 10 == 1 )
        printf("%i ", bucket[swc][i].front());
      bucket[swc][i].pop();
      k++;
    }
  }
}

int main() {
  read();
  solve();
  printSolution();
  return 0;
}