Submission #1221498

#	Time	Username	Problem	Language	Result	Execution time	Memory
1221498		nibert	Hieroglyphs (IOI24_hieroglyphs)	C++20	Compilation error	0 ms	0 KiB

hieroglyphs

#include <bits/stdc++.h>
using namespace std;

// Check if sequence 'small' is a subsequence of 'large'
bool is_subsequence(const vector<int>& large, const vector<int>& small) {
    int j = 0;
    for (int i = 0; i < (int)large.size() && j < (int)small.size(); ++i) {
        if (large[i] == small[j]) j++;
    }
    return j == (int)small.size();
}

vector<int> ucs(vector<int> A, vector<int> B) {
    unordered_map<int, queue<int>> pos_in_B;
    for (int i = 0; i < (int)B.size(); ++i) {
        pos_in_B[B[i]].push(i);
    }

    vector<int> result;
    int last_pos = -1;
    for (int i = 0; i < (int)A.size(); ++i) {
        int val = A[i];
        if (pos_in_B.count(val)) {
            // Remove positions <= last_pos
            while (!pos_in_B[val].empty() && pos_in_B[val].front() <= last_pos) {
                pos_in_B[val].pop();
            }
            if (!pos_in_B[val].empty()) {
                last_pos = pos_in_B[val].front();
                pos_in_B[val].pop();
                result.push_back(val);
            }
        }
    }

    if (result.empty()) return {}; // empty sequence is valid UCS

    // Check if it's universal
    // Brute-force check: if there is another LCS of the same length that is NOT a subsequence of this one, return -1
    // We'll try from B's perspective now
    unordered_map<int, queue<int>> pos_in_A;
    for (int i = 0; i < (int)A.size(); ++i) {
        pos_in_A[A[i]].push(i);
    }

    vector<int> alt_result;
    last_pos = -1;
    for (int i = 0; i < (int)B.size(); ++i) {
        int val = B[i];
        if (pos_in_A.count(val)) {
            while (!pos_in_A[val].empty() && pos_in_A[val].front() <= last_pos) {
                pos_in_A[val].pop();
            }
            if (!pos_in_A[val].empty()) {
                last_pos = pos_in_A[val].front();
                pos_in_A[val].pop();
                alt_result.push_back(val);
            }
        }
    }

    if (alt_result != result && (!is_subsequence(result, alt_result) || !is_subsequence(alt_result, result))) {
        return {-1}; // multiple valid common subsequences not nested inside each other
    }

    return result;
}

int main() {
    int N, M;
    cin >> N >> M;
    vector<int> A(N), B(M);
    for (int i = 0; i < N; ++i) cin >> A[i];
    for (int i = 0; i < M; ++i) cin >> B[i];

    vector<int> ans = ucs(A, B);
    cout << ans.size() << endl;
    for (int x : ans) cout << x << " ";
    cout << endl;
    return 0;
}

Compilation message (stderr)

/usr/bin/ld: /tmp/ccfpey2e.o: in function `main':
grader.cpp:(.text.startup+0x0): multiple definition of `main'; /tmp/ccFAN3Eb.o:hieroglyphs.cpp:(.text.startup+0x0): first defined here
collect2: error: ld returned 1 exit status