Cod sursa(job #1179109)

Utilizator andreiiiiPopa Andrei andreiiii Data 27 aprilie 2014 23:19:39
Problema Radix Sort Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.31 kb
#include <algorithm>
#include <fstream>
#include <cstring>
#include <vector>
#define get_byte(x) ((x>>(byte * 8))&0xFF)

using namespace std;

ifstream fin("radixsort.in");
ofstream fout("radixsort.out");

void count_sort(vector <int>::iterator begin, vector<int>::iterator end, vector<int>::iterator dest, int byte)
{
    int counter[1<<8], index[1<<8];
    memset(counter, 0, sizeof(counter));

    for(vector<int>::iterator it=begin;it!=end;it++)
        counter[get_byte(*it)]++;

    index[0]=0;
    for(int i=1;i<(1<<8);i++)
        index[i]=index[i-1]+counter[i-1];

    for(vector<int>::iterator it=begin;it!=end;it++)
        *(dest+index[get_byte(*it)]++)=*it;

}

void radix_sort(vector <int>::iterator begin, vector<int>::iterator end)
{
    vector<int> *temp=new vector<int>(end-begin);

    for(int i=0;i<4;i++)
    {
        if(i%2==0) count_sort(begin, end, temp->begin(), i);
        else count_sort(temp->begin(), temp->end(), begin, i);
    }

    delete temp;
}

vector <int> a;

int main()
{
    int N, A, B, C;
    fin>>N>>A>>B>>C;

    a.resize(N);
    a[0]=B;
    for(int i=1;i<N;i++)
        a[i]=(1LL*a[i-1]*A+B)%C;

    radix_sort(a.begin(), a.end());

    for(int i=0;i<N;i+=10) fout<<a[i]<<" ";
    fout<<"\n";

    fin.close();
    fout.close();
}