Cod sursa(job #2898437)

Utilizator disinfoion ion disinfo Data 6 mai 2022 19:02:54
Problema Radix Sort Scor 30
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.28 kb
#include <fstream>
#include <deque>
#include <vector>

using namespace std;

deque<int> bucket[2][256];
int n, a, b, c;

void rsort(vector<int>& v) {
  int i, j, k, val;
  for (i = 0, val = b; i < n; ++i, val = (a * val + b) % c){
    bucket[0][val&0x000000ff].push_back(val);
  }
  for (i = 0; i < 256; ++i) {
    while (!bucket[0][i].empty()) {
      int &e = bucket[0][i].front();
      bucket[1][(e&0x0000ff00)>>8].push_back(e);
      bucket[0][i].pop_front();
    }
  }
  for (i = 0; i < 256; ++i) {
    while (!bucket[1][i].empty()) {
      int &e = bucket[1][i].front();
      bucket[0][(e&0x00ff0000)>>16].push_back(e);
      bucket[1][i].pop_front();
    }
  }
  for (i = 0; i < 256; ++i) {
    while (!bucket[0][i].empty()) {
      int &e = bucket[0][i].front();
      bucket[1][(e&0xff000000)>>24].push_back(e);
      bucket[0][i].pop_front();
    }
  }
  k = 0;
  for (i = 0; i < 256; ++i) {
    while (!bucket[1][i].empty()) {
      if(k++ % 10 == 0){
      		v.push_back(bucket[1][i].front());
      }
      bucket[1][i].pop_front();
    }
  }
}

int main(){
	vector<int> v;
	ifstream fin;
	ofstream fout;
	fin.open("radixsort.in");
	fout.open("radixsort.out");
	fin >> n >> a >> b >> c;


	rsort(v);
	for(auto e:v){
		fout << e << " ";
	}	
}