Pagini recente » Cod sursa (job #2456953) | Profil OaidaAlexiaJoker | Cod sursa (job #1926529) | Cod sursa (job #895637) | Cod sursa (job #502561)
Cod sursa(job #502561)
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;
}