Pagini recente » Cod sursa (job #2546495) | Cod sursa (job #1493511) | Cod sursa (job #581967) | Cod sursa (job #619310) | Cod sursa (job #3235424)
// https://www.infoarena.ro/problema/interclasari
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
using namespace std;
ifstream fin("interclasari.in");
ofstream fout("interclasari.out");
int parent(int i) { return i / 2; }
int left(int i) { return 2 * i; }
int right(int i) { return 2 * i + 1; }
void heapUp(vector<int> &arr, int i)
{
while (i > 1 && arr[parent(i)] < arr[i])
{
swap(arr[parent(i)], arr[i]);
i = parent(i);
}
}
void heapDown(vector<int> &arr, int i)
{
int n = arr.size();
int l = left(i);
int r = right(i);
int largest = i;
if (l < n && arr[l] > arr[i])
{
largest = l;
}
if (r < n && arr[r] > arr[largest])
{
largest = r;
}
if (largest != i)
{
swap(arr[i], arr[largest]);
heapDown(arr, largest);
}
}
void insertNode(vector<int> &arr, int val)
{
arr.push_back(val);
heapUp(arr, arr.size() - 1);
}
void modifyNodeValue(vector<int> &arr, int val, int newVal)
{
int n = arr.size();
int i;
for (i = 1; i < n; i++)
{
if (arr[i] == val)
{
break;
}
}
arr[i] = newVal;
heapUp(arr, i);
heapDown(arr, i);
}
void deleteNode(vector<int> &arr, int val)
{
int n = arr.size();
int i;
for (i = 1; i < n; i++)
{
if (arr[i] == val)
{
break;
}
}
swap(arr[i], arr[n - 1]);
arr.pop_back();
heapDown(arr, i);
}
void printHeap(vector<int> &arr, istream &in = cin, ostream &out = cout)
{
for (int i = 1; i < arr.size(); i++)
{
out << arr[i] << " ";
}
out << endl;
}
vector<int> maxHeapify(vector<int> &arr)
{
vector<int> maxHeap;
maxHeap.push_back(0);
for (int i = 0; i < arr.size(); i++)
{
insertNode(maxHeap, arr[i]);
}
return maxHeap;
}
int maxValue(vector<int> &arr)
{
return arr[1];
}
vector<int> deleteMax(vector<int> &arr)
{
deleteNode(arr, arr[1]);
return arr;
}
vector<int> maxHeapSort(vector<int> &arr, bool ascending = true)
{
vector<int> maxHeap = maxHeapify(arr);
vector<int> sortedArr;
while (maxHeap.size() > 1)
{
sortedArr.push_back(maxValue(maxHeap));
deleteMax(maxHeap);
}
// take out the leadig 0
// sortedArr.erase(sortedArr.begin());
if (ascending)
{
reverse(sortedArr.begin(), sortedArr.end());
}
return sortedArr;
}
vector<int> firstKMax(vector<int> &arr, int k)
{
vector<int> maxHeap = maxHeapify(arr);
vector<int> kMax;
for (int i = 0; i < k; i++)
{
kMax.push_back(maxValue(maxHeap));
deleteMax(maxHeap);
}
return kMax;
}
void printVector(vector<int> &arr, istream &in = cin, ostream &out = cout)
{
for (int i = 0; i < arr.size(); i++)
{
out << arr[i] << " ";
}
out << endl;
}
vector<int> interclassing(vector<int> &arr1, vector<int> &arr2)
{
vector<int> arr3;
vector<int> maxHeap1 = maxHeapSort(arr1);
vector<int> maxHeap2 = maxHeapSort(arr2);
while (maxHeap1.size() > 0 && maxHeap2.size() > 0)
{
if (maxHeap1[0] < maxHeap2[0])
{
arr3.push_back(maxHeap1[0]);
maxHeap1.erase(maxHeap1.begin());
}
else
{
arr3.push_back(maxHeap2[0]);
maxHeap2.erase(maxHeap2.begin());
}
}
while (maxHeap1.size() > 0)
{
arr3.push_back(maxHeap1[0]);
maxHeap1.erase(maxHeap1.begin());
}
while (maxHeap2.size() > 0)
{
arr3.push_back(maxHeap2[0]);
maxHeap2.erase(maxHeap2.begin());
}
return arr3;
}
int main()
{
int n;
fin >> n;
n--;
vector<int> arr1;
int m;
fin >> m;
while (m--)
{
int x;
fin >> x;
arr1.push_back(x);
}
while (n--)
{
fin >> m;
vector<int> arr2;
for (int i = 0; i < m; i++)
{
int x;
fin >> x;
arr2.push_back(x);
}
arr1 = interclassing(arr1, arr2);
}
fout << arr1.size() << endl;
printVector(arr1, fin, fout);
return 0;
}