Submission #1214529

#	Time	Username	Problem	Language	Result	Execution time	Memory
1214529		nibert	Hieroglyphs (IOI24_hieroglyphs)	C++20	0 / 100	1095 ms	2732 KiB

hieroglyphs

#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;

vector<int> ucs(vector<int> A, vector<int> B) {
    int N = A.size(), M = B.size();
    vector<int> prev(M + 1), curr(M + 1);

    // Build only 2 rows of DP
    for (int i = N - 1; i >= 0; --i) {
        curr.assign(M + 1, 0);
        for (int j = M - 1; j >= 0; --j) {
            if (A[i] == B[j]) {
                curr[j] = 1 + prev[j + 1];
            } else {
                curr[j] = max(prev[j], curr[j + 1]);
            }
        }
        swap(curr, prev);
    }

    // Backtrack while checking for multiple choices
    vector<int> res;
    int i = 0, j = 0;
    while (i < N && j < M) {
        if (A[i] == B[j]) {
            res.push_back(A[i]);
            i++;
            j++;
        } else {
            int skipA = (i + 1 <= N) ? prev[j] : 0;
            int skipB = (j + 1 <= M) ? prev[j + 1] : 0;
            int best = max(skipA, skipB);

            // We must recompute current dp[i][j+1] since it's not stored
            int currJ = 0;
            if (j + 1 < M) {
                if (A[i] == B[j + 1]) currJ = 1 + prev[j + 2];
                else currJ = max(prev[j + 1], 0);
            }

            // Detect multiple choices
            int cnt = 0;
            if (skipA == best) cnt++;
            if (currJ == best) cnt++;
            if (cnt > 1) return {-1};

            if (skipA == best) i++;
            else j++;
        }

        // Update prev row manually
        for (int jj = M - 1; jj >= 0; --jj) {
            if (A[i] == B[jj]) {
                curr[jj] = 1 + prev[jj + 1];
            } else {
                curr[jj] = max(prev[jj], curr[jj + 1]);
            }
        }
        swap(prev, curr);
    }

    return res;
}

• Subtask 0: 0 / 0
• Subtask 1: 0 / 3
• Subtask 2: 0 / 15
• Subtask 3: 0 / 10
• Subtask 4: 0 / 16
• Subtask 5: 0 / 14
• Subtask 6: 0 / 42