Cod sursa(job #3287363)

Utilizator nurof3nCioc Alex-Andrei nurof3n Data 17 martie 2025 17:03:07
Problema Cel mai lung subsir comun Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 4.21 kb
// https://www.infoarena.ro/problema/cmlsc
#include <iostream>
#include <fstream>
#include <tuple>
#include <vector>

struct dp_info
{
    int i, j, len;

    dp_info& operator=(dp_info other) noexcept
    {
        std::swap(i, other.i);
        std::swap(j, other.j);
        std::swap(len, other.len);
        return *this;
    }

    bool is_empty() const
    {
        return i == 0 && j == 0;
    }
};

template <class T>
class Vector2D
{
public:
    Vector2D(unsigned rows, unsigned cols) : m_rows(rows), m_cols(cols)
    {
        if (rows == 0 || cols == 0)
            throw std::underflow_error("Vector2D dimensions cannot be 0");
        m_data = new T[m_rows * m_cols];
    }
    ~Vector2D()
    {
        delete[] m_data;
    }

    inline T& operator()(unsigned row, unsigned col)
    {
        if (row >= m_rows || col >= m_cols)
            throw std::overflow_error("Vector2D subscript out of bounds");
        return m_data[m_cols * row + col];
    }
    inline T operator()(unsigned row, unsigned col) const
    {
        if (row >= m_rows || col >= m_cols)
            throw std::overflow_error("Vector2D subscript out of bounds");
        return m_data[m_cols * row + col];
    }

private:
    unsigned m_rows{};
    unsigned m_cols{};

    T* m_data;
};

int cmlsc_with_pairs(int vm[], int m, int vn[], int n, int vsol[])
{
    auto empty = dp_info{ 0, 0, 0 };

    Vector2D<dp_info> dp(m + 1, n + 1);
    dp(0, 0) = dp(0, 1) = dp(1, 0) = empty;
    if (vm[0] == vn[0])
        dp(1, 1) = { 1, 1, 1 };
    else
        dp(1, 1) = empty;

    for (int i = 2; i <= m; ++i)
        if (dp(i - 1, 1).is_empty() && vm[i - 1] == vn[0])
            dp(i, 1) = { i, 1, 1 };
        else
            dp(i, 1) = dp(i - 1, 1);

    for (int j = 2; j <= n; ++j)
        if (dp(1, j - 1).is_empty() && vm[0] == vn[j - 1])
            dp(1, j) = { 1, j, 1 };
        else
            dp(1, j) = dp(1, j - 1);

    for (int i = 2; i <= m; ++i)
        for (int j = 2; j <= n; ++j) {
            bool first_cond  = dp(i - 1, j).j == j;
            bool second_cond = dp(i, j - 1).i == i;
            if (first_cond && second_cond) {
                if (dp(i - 1, j).len < dp(i, j - 1).len)
                    dp(i, j) = dp(i, j - 1);
                else
                    dp(i, j) = dp(i - 1, j);
            }
            else if (first_cond)
                dp(i, j) = dp(i - 1, j);
            else if (second_cond)
                dp(i, j) = dp(i, j - 1);
            else if (vm[i - 1] == vn[j - 1])
                dp(i, j) = { i, j, dp(i - 1, j - 1).len + 1 };
            else
                dp(i, j) = dp(i - 1, j - 1);
        }

    int  len      = dp(m, n).len;
    auto last_pos = dp(m, n);
    while (!last_pos.is_empty()) {
        vsol[--len] = vm[last_pos.i - 1];
        last_pos    = dp(last_pos.i - 1, last_pos.j - 1);
    }

    return dp(m, n).len;
}

int cmlsc(int vm[], int m, int vn[], int n, int vsol[])
{
    Vector2D<int> dp(m + 1, n + 1);
    for (int i = 0; i <= m; ++i)
        dp(i, 0) = 0;
    for (int j = 1; j <= n; ++j)
        dp(0, j) = 0;

    for (int i = 1; i <= m; ++i)
        for (int j = 1; j <= n; ++j)
            if (vm[i - 1] == vn[j - 1])
                dp(i, j) = 1 + dp(i - 1, j - 1);
            else
                dp(i, j) = std::max(dp(i - 1, j), dp(i, j - 1));

    int len = dp(m, n), sol_len = len;
    while (m > 0 && n > 0 && dp(m, n) > 0) {
        if (vm[m - 1] == vn[n - 1])
            vsol[--len] = vm[m - 1], --m, --n;
        else if (dp(m - 1, n) == dp(m, n))
            --m;
        else
            --n;
    }

    return sol_len;
}

int main()
{
    try {
        std::ifstream in("cmlsc.in");
        std::ofstream out("cmlsc.out");

        if (!in.is_open())
            throw std::runtime_error("input file not found");

        int m, n;
        in >> m >> n;

        int vm[1025], vn[1025];
        for (int i = 0; i < m; ++i)
            in >> vm[i];
        for (int i = 0; i < n; ++i)
            in >> vn[i];

        int sol_len, vsol[1025];
        sol_len = cmlsc(vm, m, vn, n, vsol);
        out << sol_len << '\n';
        for (int i = 0; i < sol_len; ++i)
            out << vsol[i] << ' ';
    }
    catch (const std::exception& e) {
        std::cerr << e.what();
        return EXIT_FAILURE;
    }
}