Cod sursa(job #1189164)

Utilizator xtreme77Patrick Sava xtreme77 Data 21 mai 2014 17:41:12
Problema Radix Sort Scor 30
Compilator cpp Status done
Runda Arhiva educationala Marime 0.89 kb
//SPadix Sort
//Copyright to Sava Patrick

#include <cstdio>
#include <vector>
#include <algorithm>
const int MAX=10000100;
using namespace std;
vector <int> v;
int main()
{
    int a,b,c,n;
    freopen("radixsort.in","r",stdin);
    freopen("radixsort.out","w",stdout);
    scanf("%d%d%d%d",&n,&a,&b,&c);
    v.push_back(0);
    v.push_back(b);
    for(int i=2;i<=n;++i){
        int x=(1LL*a*v[i-1]+b)%c;
        v.push_back(x);
    }
    nth_element(v.begin()+1,v.begin()+(3*n/4),v.end());
    nth_element(v.begin()+1,v.begin()+(n/2),v.begin()+(3*n/4));
    nth_element(v.begin()+1,v.begin()+(n/4),v.begin()+(n/2));
    sort(v.begin()+1,       v.begin()+(n/4));

    sort(v.begin()+(n/4),   v.begin()+(n/2));

    sort(v.begin()+(n/2),   v.begin()+(3*n/4));

    sort(v.begin()+(3*n/4), v.end());

    for(int i=1;i<=n;printf("%d ",v[i]),i+=10);printf("\n");
    return 0;
}