Submission #1221497

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

hieroglyphs

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

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

    // greedy build one LCS
    vector<int> candidate;
    int last_index = -1;
    for (int x : A) {
        if (!pos_in_B.count(x)) continue;
        // binary search for first position > last_index
        auto& vec = pos_in_B[x];
        auto it = upper_bound(vec.begin(), vec.end(), last_index);
        if (it != vec.end()) {
            last_index = *it;
            candidate.push_back(x);
        }
    }

    // verify universal
    // brute force: all common subsequences are subsequences of `candidate`
    // simulate all possible small subsequences and check (use map count to limit)
    unordered_map<string, bool> seen;
    function<void(int, int, string, bool&)> dfs = [&](int i, int j, string s, bool& ok) {
        if (i == A.size() || j == B.size()) {
            if (!seen[s] && s.size() > 0) {
                seen[s] = true;
                // check if s is a subsequence of candidate
                int k = 0;
                for (char ch : s) {
                    while (k < candidate.size() && candidate[k] != (ch - '0')) k++;
                    if (k == candidate.size()) {
                        ok = false;
                        return;
                    }
                    k++;
                }
            }
            return;
        }
        if (A[i] == B[j]) {
            dfs(i + 1, j + 1, s + (char)('0' + A[i]), ok);
        }
        dfs(i + 1, j, s, ok);
        dfs(i, j + 1, s, ok);
    };

    if (candidate.empty()) return {}; // valid, UCS is []

    // only run full check for small input to avoid TLE
    if (A.size() <= 10 && B.size() <= 10) {
        bool ok = true;
        dfs(0, 0, "", ok);
        if (!ok) return {-1};
    }

    return candidate;
}

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> res = ucs(A, B);
    cout << res.size() << endl;
    for (int x : res) cout << x << " ";
    cout << endl;
}

Compilation message (stderr)

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