Cod sursa(job #3166055)

Utilizator dragoncrackCandidatu Mario Luca dragoncrack Data 7 noiembrie 2023 16:50:31
Problema Cel mai lung subsir comun Scor 30
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 3.18 kb
#include <fstream>
#include <vector>
#define DIM 1025
#define LIMIT 256

using namespace std;

ifstream fin("cmlsc.in");
ofstream fout("cmlsc.out");

struct subsir {
    int head;
    int positionB;
    int positionA;
    int length;
    int previous;

    subsir() {
        head = 0;
        positionA = -1;
        positionB = -1;
        length = 0;
        previous = -1;
    }
};

int n, m;
int A[DIM], B[DIM];
vector<int> positionsInB[LIMIT + 1];
vector<subsir> subsiruri;

int findBestPosition(int prevPositionB, int directoryIndex) {
    int position = -1;
    int st = 0;
    int dr = positionsInB[directoryIndex].size() - 1;
    while (st <= dr) {
        int mid = (st + dr) / 2;
        if (positionsInB[directoryIndex][mid] > prevPositionB) {
            dr = mid - 1;
            position = positionsInB[directoryIndex][mid];
        }
        else {
            st = mid + 1;
        }
    }
    if (position < prevPositionB)
    {
        position = -1;
    }
    return position;
}

void printSubsir(subsir current) {
    if (current.previous != -1) {
        printSubsir(subsiruri[current.previous]);
    }
    fout << current.head << " ";
}

int main()
{
    fin >> n >> m;
    for (int i = 1; i <= n; i++) {
        fin >> A[i];
    }
    for (int i = 1; i <= m; i++) {
        fin >> B[i];
        positionsInB[B[i]].push_back(i);
    }
    for (int i = 1; i <= n; i++) {
        if (positionsInB[A[i]].size() == 0)
            continue;
        int place = -1;
        int maxLength = -1;
        int previousIndex = -1;
        for (vector<subsir> ::iterator it = subsiruri.begin(); it != subsiruri.end(); it++) {
            if (it->length + 1 < maxLength)
                continue;
            int placeInB = findBestPosition(it->positionB, A[i]);
            if (placeInB != -1) {
                if (maxLength < it->length + 1) {
                    maxLength = it->length + 1;
                    place = placeInB;
                    previousIndex = it - subsiruri.begin();
                }
                else if (maxLength == it->length + 1) {
                    if (place > placeInB) {
                        place = placeInB;
                        previousIndex = it - subsiruri.begin();
                    }
                }
            }
        }
        subsir newSubsir;
        if (maxLength != -1) {
            newSubsir.head = A[i];
            newSubsir.positionA = i;
            newSubsir.positionB = place;
            newSubsir.previous = previousIndex;
            newSubsir.length = maxLength;
        }
        else {
            newSubsir.head = A[i];
            newSubsir.positionA = i;
            newSubsir.positionB = positionsInB[A[i]][0];
            newSubsir.previous = -1;
            newSubsir.length = 1;
        }
        subsiruri.push_back(newSubsir);
    }
    int sol = -1;
    subsir maxSubsirEnd;
    for (vector<subsir> ::iterator it = subsiruri.begin(); it != subsiruri.end(); it++) {
        if (sol < it->length) {
            sol = it->length;
            maxSubsirEnd = *it;
        }
    }
    fout << sol << "\n";
    printSubsir(maxSubsirEnd);
}