Cod sursa(job #992775)

Utilizator AlexandruValeanuAlexandru Valeanu AlexandruValeanu Data 2 septembrie 2013 16:06:05
Problema Interclasari Scor 90
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.3 kb
#include <iostream>
#include <fstream>
#include <list>
#include <queue>
#include <algorithm>

using namespace std;

const int Nmax = 1000002;
const int Kmax = 22;

typedef pair<int,short> node;

list <int> G[Kmax];

priority_queue < node, vector <node>, greater <node> > MinHeap;

int N, K, Sum;

void read()
{
    ifstream f("interclasari.in");

    f >> K;

    for ( int i = 1; i <= K; ++i )
    {
        f >> N;

        for ( int j = 1, elem; j <= N; ++j )
                f >> elem,
                G[i].push_back( elem );

        Sum += N;
    }

    f.close();
}

void init_heap()
{
    for ( int i = 1; i <= K; ++i )
    {
        if ( G[i].size() )
        {
            MinHeap.push( node( G[i].front(), i ) );
            G[i].pop_front();
        }
    }
}

void solve()
{
    ofstream g("interclasari.out");

    g << Sum << "\n";

    while ( !MinHeap.empty() )
    {
        int nod = MinHeap.top().first;
        int ind = MinHeap.top().second;

        g << nod << " ";

        MinHeap.pop();

        if ( G[ind].size() )
        {
            MinHeap.push( node( G[ind].front(), ind ) );
            G[ind].pop_front();
        }
    }

    g.close();
}

int main()
{
    read();
    init_heap();
    solve();

    return 0;
}