Pagini recente » Cod sursa (job #3278458) | Cod sursa (job #968722) | Cod sursa (job #1169422) | Cod sursa (job #1841116) | Cod sursa (job #3291299)
#include <iostream>
#include <fstream>
using namespace std;
ifstream f("interclasari.in");
ofstream g("interclasari.out");
int i,j,perechi,k,aux,m[21][100001],v[100001],vi[100001],ma,sz;
struct H{
int lin, val,index;
}h[21],mii;
int parinte(int pos)
{
return pos/2;
}
void urcare(int pos)
{
while(pos>1&&h[parinte(pos)].val>h[pos].val)
{
swap(h[parinte(pos)],h[pos]);
pos=parinte(pos);
}
}
void inserare(int x,int l,int i)
{
sz++;
h[sz].val=x;
h[sz].lin=l;
h[sz].index=i;
urcare(sz);
}
int left_son(int pos)
{
return 2*pos;
}
int right_son(int pos)
{
return 2*pos+1;
}
void coborare(int pos)
{
while(true)
{
//verific daca nodul este frunza
if(left_son(pos)>sz)
{
break;
}
//singurul nod posibil existent este cel stang
int next_pos=left_son(pos);
if(right_son(pos)<=sz&&h[right_son(pos)].val<h[next_pos].val)
next_pos=right_son(pos);
if(h[pos].val>h[next_pos].val)
{
swap(h[pos],h[next_pos]);
pos=next_pos;
}
else
break;
}
}
void sterge_minim()
{
swap(h[1],h[sz]);
sz--;
coborare(1);
}
H minim()
{
return h[1];
}
int main()
{
f>>perechi;
while(perechi)
{
f>>k;
if(k!=0)
{
aux++;
for(i=1;i<=k;++i)
{
f>>m[aux][i];
}
v[aux]=k;
vi[aux]=k;
if(k>ma)
ma=k;
}
perechi--;
}
for(j=1;j<=aux;++j)
inserare(m[j][1],j,1);
mii=minim();
g<<mii.val<<' ';
sterge_minim();
v[mii.lin]--;
int ok=1;
while(v[mii.lin]!=0&&ok==1)
{
if(mii.index + 1 <= v[mii.lin])
{
inserare(m[mii.lin][mii.index+1], mii.lin, mii.index+1);
v[mii.lin]--;
mii=minim();
cout<<mii.val<<' ';
sterge_minim();
}
//primulvector in care inca mai este ceva
else
{
for(i=1;i<=aux;++i)
if(v[i]!=0)
{
ok=1;
inserare(m[i][vi[i]-v[i]+1], i, vi[i]-v[i]+1);
v[i]--;
mii=minim();
g<<mii.val<<' ';
sterge_minim();
}
else
ok=0;
}
}
for(i=1;i<=aux;++i)
if(v[i]!=0)
{
g<<m[i][vi[i]];
}
return 0;
}