Cod sursa(job #1424759)

Utilizator UAIC_HreapcaVlasNegrusUAIC Hreapca Vlas Negrus UAIC_HreapcaVlasNegrus Data 25 aprilie 2015 14:53:59
Problema Radix Sort Scor 30
Compilator cpp Status done
Runda Arhiva educationala Marime 1.25 kb
#include <iostream>
#include <deque>
#include <vector>
#include <cstring>
#include <bitset>
#include <algorithm>
#define INF 1000010
#define uint unsigned int
#define ll long long
#define step(x) (x&(-x))
using namespace std;

int N, A, B, C, i;
vector<int> v, sol;

void radixsort(vector<int> &V, int step)
{
    if(step == 4)
    {
        for(vector<int>::iterator it = V.begin(); it!=V.end(); it++)
            sol.push_back(*it);
        return;
    }
    vector<int> chunk[257];
    int st = 32 - (step + 1) * 8;
    for(vector<int>::iterator it = V.begin(); it!=V.end(); it++)
    {
        int x = *it;
        int nr = 0;
        for(int i = 0; i < 8; i++)
        {
            if(x & (1<<(st+i)))
                nr = nr + (1<<i);
        }
        chunk[nr].push_back(x);
    }
    for(int i = 0; i < 257; i++)
        if(chunk[i].size())
        {
            radixsort(chunk[i], step + 1);
            chunk[i].clear();
        }
}


int main()
{
    freopen("radixsort.in","r",stdin);
    freopen("radixsort.out","w",stdout);
    scanf("%d%d%d%d", &N, &A, &B, &C);
    v.push_back(B);
    for(i = 1; i < N; i++)
        v.push_back((A * v[i-1] + B) % C);
    radixsort(v, 0);
    for(i = 0; i < sol.size(); i+=10)
        printf("%d ",sol[i]);
    return 0;
}