Cod sursa(job #2195457)

Utilizator llalexandruLungu Alexandru Ioan llalexandru Data 16 aprilie 2018 13:55:54
Problema Radix Sort Scor 30
Compilator cpp Status done
Runda Arhiva educationala Marime 1.08 kb
#include <iostream>
#include <cstdio>
#include <map>

using namespace std;

struct nod{int val; map<int, nod*> V;};

int n, a, b, c;
nod* tata;

void Add(nod* node, int x, int nr)
{
    if (nr==-1)
    {
        node->val++;
        return;
    }
    int b = (x>>(8*nr))%256;
    if (node->V.find(b)==node->V.end())
        node->V[b] = new nod();
    Add(node->V[b], x, nr-1);
}

int trb=1;

void DFS(nod* node, int lvl, int x)
{
    if (lvl==-1)
    {
        for(int i=1; i<=node->val; i++)
        {
            if (trb%10==1)
                cout<<(x>>8)<<" ";
            trb++;
        }
    }
    for (map<int, nod*>::iterator it=node->V.begin(); it!=node->V.end(); it++)
    {
        DFS(it->second, lvl-1, (x+it->first)<<8);
    }
}

int main()
{
    freopen("radixsort.in", "r", stdin);
    freopen("radixsort.out", "w", stdout);
    cin>>n>>a>>b>>c;
    tata = new nod();
    int x=b;
    Add(tata, x, 3);
    for (int i=2; i<=n; i++)
    {
        x=(a*x+b)%c;
        Add(tata, x, 3);
    }
    DFS(tata, 3, 0);
    return 0;
}