Cod sursa(job #502561)

Utilizator APOCALYPTODragos APOCALYPTO Data 20 noiembrie 2010 01:21:06
Problema Zeap Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.03 kb
using namespace std;

#include<iostream>
#include<fstream>
#include<ctime>
#include<cstdlib>
#define oo 0x3f3f3f3f
#define ba(x) this->x=x
struct T{
int key,p,sbt;
T *left,*right;
T(){}
T(int key,int p,T* right,T*left,int sbt)
{
    ba(key);
    ba(p);
    ba(right);
    ba(left);
    ba(sbt);

}};
T *R,*nil;
int N,M,a[100],sum=0,su=0;
ofstream fout("numar2.out");
void init()
{
    R=nil=new T(0,-oo,NULL,NULL,0);
}

void update(T* &n)
{


    n->sbt=1;
    if(n->left!=nil)
    n->sbt+=n->left->sbt;
    if(n->right!=nil)
    n->sbt+=n->right->sbt;

}



void rotleft(T* &n)
{
    T* t=n->left;
    n->left=t->right;
    t->right=n;
    n=t;
}

void rotright(T* &n)
{
    T* t=n->right;
    n->right=t->left;
    t->left=n;
    n=t;
}
void balance(T* &n)
{

    if(n->p<n->left->p) {rotleft(n); update(n->right); update(n);}
    if(n->p<n->right->p) {rotright(n);  update(n->left);  update(n);}

}

void insert(int key,T* &n)
{
    if(n->key==key) return;
    if(n==nil)
    {
        n=new T(key,rand(),nil,nil,1);
        return;

    }
    if(key<n->key) insert(key,n->left);
    if(key>n->key) insert(key,n->right);
    update(n);
    balance(n);
}

void parcurgere(T* &n)
{
    if(n->left!=nil)
     parcurgere(n->left);
     su++;


    cout<<su<<" "<<n->key<<" "<<n->sbt<<"\n";

    if(n->right!=nil)
     parcurgere(n->right);

}

void cauta(T* &n)
{


    if(n->left->sbt+sum+1==M) {fout<<n->key<<" "; return;}
    if(n->left->sbt+sum+1>M)  cauta(n->left);
    if(n->left->sbt+sum+1<M) sum+=1+n->left->sbt,cauta(n->right);
}



void solve()
{int i,j;

    for(i=1;i<=N;i++)
    {
        for(j=1;j<=M;j++)

         {insert(a[i]*j,R);

         }
    }

        //parcurgere(R);
        cauta(R);
}

void cit()
{int i;
    ifstream fin("numar2.in");
    fin>>N>>M;
    for(i=1;i<=N;i++)
     fin>>a[i];
    fin.close();
}

int main()
{
    srand(time(0));
    init();

    cit();
    solve();
    fout.close();
    return 0;

}