Cod sursa(job #1602886)

Utilizator preda.andreiPreda Andrei preda.andrei Data 16 februarie 2016 23:09:54
Problema Interclasari Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.97 kb
#include <iostream>
#include <cstdio>
#include <vector>

using namespace std;

vector<int> v;

void interschimba(int &a, int &b){
    int aux = a;
    a = b;
    b = aux;
}

int tata(int k){
    return k / 2;
}

int fiuStanga(int k){
    return 2 * k;
}

int fiuDreapta(int k){
    return 2 * k + 1;
}

void sita(int k, int n){
    int f1, f2;
    bool gata;

    gata = false;
    while(!gata){
        f1 = fiuStanga(k);
        f2 = fiuDreapta(k);

        if(f2 <= n && v[f2] > v[f1])
            f1 = f2;

        if(f1 <= n && v[k] < v[f1]){
            interschimba(v[k], v[f1]);
            k = f1;
        }
        else gata = true;
    }
}

void percolate(int k){
    int t = tata(k);

    while(t > 0 && v[t] < v[k]){
        interschimba(v[t], v[k]);
        k = t;
        t = tata(k);
    }
}

void construiesteHeap(int n){
    for(int i = n / 2; i > 0; --i){
        sita(i, n);
    }
}

void adaugaInHeap(int x, int &n){
    n++;
    v.push_back(x);
    percolate(n);
}

void heapsort(int n){
    for(int i = n; i >= 1; --i){
        interschimba(v[1], v[i]);
        sita(1, i - 1);
    }
}

int main()
{
    FILE *fin = fopen("interclasari.in", "r");
    FILE *fout = fopen("interclasari.out", "w");

    int echipe, n, ntot = 0, x;

    fscanf(fin, "%d", &echipe);
    v.push_back(0);
    for(int i = 1; i <= echipe; ++i){
        fscanf(fin, "%d", &n);
        for(int j = 1; j <= n; ++j){
            fscanf(fin, "%d", &x);
            if(i > 1)
                adaugaInHeap(x, ntot);
            else v.push_back(x);
        }
        if(i == 1){
            ntot = n;
            construiesteHeap(ntot);
//            for(int i= 1; i <= ntot; ++i)
//                fprintf(fout, "%d ", v[i]);
//            fprintf(fout, "\n");
        }
    }

    heapsort(ntot);

    fprintf(fout, "%d\n", ntot);
    for(int i = 1; i <= ntot; ++i)
        fprintf(fout, "%d ", v[i]);

    return 0;
}