Cod sursa(job #1684563)

Utilizator pickleVictor Andrei pickle Data 11 aprilie 2016 10:06:11
Problema Radix Sort Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.44 kb
#include <algorithm>
#include <bitset>
#include <cmath>
#include <fstream>
#include <iostream>
#include <queue>
#include <stack>
#include <string.h>
#include <string>
#include <vector>

using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
ifstream fin ("radixsort.in");
ofstream fout ("radixsort.out");
const int INF = 0x3f3f3f3f;
const int Nmax = 10000777;

int N, A, B, C;

queue<int> bucket[2][256];
int a[Nmax];

int main() {
  fin >> N >> A >> B >> C;
  a[0] = B;
  for(int i = 1; i < N; ++i)
    a[i] = (1ll * A * a[i-1] + B) % C;

  for (int i = 0; i < N; ++i) {
    bucket[0][a[i] & 0x000000ff].push(a[i]);
  }
  for (int b = 0; b < 256; ++b) {
    while(!bucket[0][b].empty()) {
      int &e = bucket[0][b].front();
      bucket[1][(e & 0x0000ff00) >> 8].push(e);
      bucket[0][b].pop();
    }
  }

  for (int b = 0; b < 256; ++b) {
    while(!bucket[1][b].empty()) {
      int &e = bucket[1][b].front();
      bucket[0][(e & 0x00ff0000) >> 16].push(e);
      bucket[1][b].pop();
    }
  }

  for (int b = 0; b < 256; ++b) {
    while(!bucket[0][b].empty()) {
      int &e = bucket[0][b].front();
      bucket[1][(e & 0xff000000) >> 24].push(e);
      bucket[0][b].pop();
    }
  }

  int cnt = 0;
  for (int b = 0; b < 256; ++b) {
    while(!bucket[1][b].empty()) {
      a[cnt] = bucket[1][b].front();
      bucket[1][b].pop();
      cnt++;
    }
  }

  for (int i = 0; i < N; i += 10) {
    fout << a[i] << ' ';
  }
  fout << endl;


  return 0;
}