Pagini recente » Cod sursa (job #2131996) | Cod sursa (job #1092097) | Cod sursa (job #1973508) | Cod sursa (job #3219959) | Cod sursa (job #1602886)
#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;
}