Cod sursa(job #1424825)

Utilizator UAIC_HreapcaVlasNegrusUAIC Hreapca Vlas Negrus UAIC_HreapcaVlasNegrus Data 25 aprilie 2015 15:49:29
Problema Radix Sort Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.43 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;

uint N, A, B, C, i, cnt, mask[4], j;
vector<uint> v;

void radixsort(vector<uint> &V, uint step)
{
    if(step == 4)
    {
        for(vector<uint>::iterator it = V.begin(); it!=V.end(); it++)
        {
            cnt = cnt + 1;
            if(cnt % 10 == 1)
                printf("%d ",*it);
        }
        return;
    }
    vector<uint> chunk[257];
    for(vector<uint>::iterator it = V.begin(); it!=V.end(); it++)
    {
        uint x = *it;
        uint nr = (mask[step] & x) >> ((3-step)*8);
        chunk[nr].push_back(x);
    }
    for(uint i = 0; i < 256; i++)
    {
        if(chunk[i].size() > 1)
        {
            radixsort(chunk[i], step + 1);
            chunk[i].clear();
        }
        if(chunk[i].size() == 1)
        {
            cnt = cnt + 1;
            if(cnt % 10 == 1)
                printf("%d ",*it);
        }
}


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