Submission #1221505

#	Time	Username	Problem	Language	Result	Execution time	Memory
1221505		nibert	Hieroglyphs (IOI24_hieroglyphs)	C++20	3 / 100	233 ms	146864 KiB

hieroglyphs

#include <iostream>
#include <vector>
#include <unordered_map>
#include <queue>
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)) {
            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

    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}; // no unique UCS
    }

    return result;
}

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