Cod sursa(job #1493220)

Utilizator deea101Andreea deea101 Data 28 septembrie 2015 21:15:06
Problema Radix Sort Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.89 kb
#include <fstream>
#include <iostream>
#include <cstring>
#include <vector>
using namespace std;
  
ifstream f("radixsort.in");
ofstream g("radixsort.out");

void radix_sort(vector <int> &v) {
	int i, j;
	int counter[1<<8];

	vector <int> backup(v);
	for(i = 0; i < 32; i+=8) {
		memset(counter, 0, sizeof(counter));
		for(j = 0; j < v.size(); j++) {
			counter[(v[j]>>i) & 255]++;
			backup[j] = v[j];
		}
			
		for(j = 1; j < 256; j++) 
			counter[j] += counter[j-1];
		
		for(j = v.size()-1; j>=0; j--) {
			counter[(backup[j]>>i) & 255] --;
			v[counter[(backup[j]>>i) & 255]] = backup[j];
		}
	}
}

int main() {
	int N;
    f>>N;
	vector <int> v(N);
  
    int A,B,C;
    f>>A>>B>>C;
      
    v[0] = B;
    for(int i = 1; i < N ; i++)
    {
        v[i]=(1LL*A*v[i-1]+B)%C;
    }

	radix_sort(v);
	for(int i = 0; i < N; i += 10)
        g<<v[i]<<' ';
}