Cod sursa(job #3291299)

Utilizator mariuckkaTanasoiu Maria Alexia mariuckka Data 4 aprilie 2025 00:56:32
Problema Interclasari Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.56 kb
#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;
}