Cod sursa(job #1786489)

Utilizator whoiscrisCristian Plop whoiscris Data 23 octombrie 2016 01:09:28
Problema Radix Sort Scor 30
Compilator cpp Status done
Runda Arhiva educationala Marime 2.84 kb
#include <map>
#include <set>
#include <list>
#include <cmath>
#include <ctime>
#include <deque>
#include <queue>
#include <stack>
#include <string>
#include <bitset>
#include <cstdio>
#include <limits>
#include <vector>
#include <climits>
#include <cstring>
#include <cstdlib>
#include <fstream>
#include <numeric>
#include <sstream>
#include <iostream>
#include <algorithm>
#include <unordered_map>
#include <bitset>
#include <utility>

#define rep(i,a,b) for(int i=int(a); i<=int(b); ++i)
#define rev(i,b,a) for(int i=int(b); i>=int(a); --i)
#define rec(i,a,b,c) for(int i=int(a); i<=int(b); i+=int(c))
#define recv(i,a,b,c) for(int i=int(a); i>=int(b); i-=int(c))
#define mp(x,y) make_pair((x),(y))
#define pb(x) push_back(x)
#define all(c) c.begin(), c.end()
#define tr(container, it) for(auto it=(container).begin(); it != (container).end(); ++it)
#define sqr(x) ((x)*(x))
#define sz(a) int((a).size())
#define mod(a,n) ((a) < 0 ? ((n)+(a)) : ((a)%(n)))
#define mout(M,n,m) rep(i,0,(n)-1){ rep(j,0,(m)-1) cout << (M)[i][j] << " ";  cout << "\n"; }
#define vout(A,l,r) rep(i,l,r) cout << A[i] << " "; cout << "\n";
using namespace std;

#define INF_ULL ULLONG_MAX
#define INF_LL  LLONG_MAX
#define NINF_LL LLONG_MIN
#define INF_L   LONG_MAX
#define NINF_L   LONG_MIN
#define INF_U   UINT_MAX
#define INF     INT_MAX
#define NINF     INT_MIN

typedef vector<int> vi;
typedef pair<int, int> ii;
typedef vector<ii> vii;
typedef long long ll;
typedef unsigned long ul;

#define ONES_BYTE 0xFF
vector<ul> V, temp;
vector<ul> buckets(256,0);
int N,A,B,C;

inline ul key(ul value, ul exp){
  return ((value >> (exp * 8)) & ONES_BYTE);
}

void count_sort(int exp){
  rep(i,0,buckets.size()-1)
    buckets[i] = 0;

  rep(i,0,V.size()-1)
    buckets[key(V[i], exp)]++;

  // cumulative count so that buckets points to final position
  //rep(i,1,buckets.size()-1)
    //buckets[i] += buckets[i-1];

  vector<ul> index(N,0);
  index[0] = 0;
   for(int i = 1; i < 256; i++)
       index[i] = index[i-1] + buckets[i-1];

  // write elements sorted by exp into temporary array
  for(int i=0; i<temp.size(); ++i){
    temp[index[key(V[i], exp)]++] = V[i];
    //buckets[key(V[i], exp)]++;
  }

  rep(i,0,V.size()-1)
    V[i] = temp[i];
}

void radix_sort(){
  rep(exp,0,3)
    count_sort(exp);
}

int main(){

  freopen("radixsort.in", "r", stdin);
  //freopen("grader_test7.in", "r", stdin);
  freopen("radixsort.out", "w", stdout);

  // read data
  cin >> N >> A >> B >> C;
  V.resize(N,0);
  temp.resize(N,0);
  V[0] = B;
  rep(i,1,N-1)
    V[i] = ((1UL * A * V[i-1]) % C + B) % C;

  /*
  vector<ul> V_sorted = V;
  sort(V_sorted.begin(), V_sorted.end());
  cout << "sorted with quicksort:\n";
  vout(V_sorted, 0, N-1)
  */

  //vout(V,0,N-1)
  radix_sort();
  //cout << "sorted with radixsort:\n";
  //vout(V,0,N-1)

  // output
  for(int i=0; i<N; i+=10)
    cout << V[i] << " ";
  cout << "\n";

  return 0;
}