Cod sursa(job #3235424)

Utilizator PetstebPopa Petru Petsteb Data 17 iunie 2024 20:20:25
Problema Interclasari Scor 40
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 4.3 kb
// 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;
}