Submission #1221535

#	Time	Username	Problem	Language	Result	Execution time	Memory
1221535		nibert	Hieroglyphs (IOI24_hieroglyphs)	C++20	0 / 100	1129 ms	1052916 KiB

hieroglyphs

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

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

    // Map value -> list of positions in B (1-indexed for Fenwick tree)
    unordered_map<int, vector<int>> posB;
    for (int i = 0; i < M; i++)
        posB[B[i]].push_back(i + 1);

    vector<int> seq;
    for (int i = N - 1; i >= 0; i--) {
        auto it = posB.find(A[i]);
        if (it != posB.end()) {
            const vector<int>& positions = it->second;
            for (int j = (int)positions.size() - 1; j >= 0; --j) {
                seq.push_back(positions[j]);
            }
        }
    }

    reverse(seq.begin(), seq.end());
    if (seq.empty()) return {};

    // Fenwick tree for LIS
    int max_val = M + 2;
    vector<int> dp(max_val, 0), count(max_val, 0);

    int best_len = 0, best_cnt = 0;
    unordered_map<int, pair<int, int>> last;
    for (int val : seq) {
        int mx = 0, cnt = 1;
        for (int x = val - 1; x > 0; x -= x & -x)
            if (dp[x] > mx) {
                mx = dp[x];
                cnt = count[x];
            } else if (dp[x] == mx) {
                cnt += count[x];
            }

        int new_len = mx + 1;

        for (int x = val; x < max_val; x += x & -x) {
            if (dp[x] < new_len) {
                dp[x] = new_len;
                count[x] = cnt;
            } else if (dp[x] == new_len) {
                count[x] += cnt;
            }
        }

        last[val] = {new_len, cnt};
        if (new_len > best_len) {
            best_len = new_len;
            best_cnt = cnt;
        } else if (new_len == best_len) {
            best_cnt += cnt;
        }
    }

    if (best_cnt > 1) return {-1};

    // Reconstruct the unique LIS (UCS)
    vector<int> ucs_sequence;
    int len = best_len;
    int last_pos = max_val;

    for (int i = seq.size() - 1; i >= 0; i--) {
        int val = seq[i];
        if (val < last_pos && last[val].first == len) {
            ucs_sequence.push_back(val);
            last_pos = val;
            len--;
        }
    }

    reverse(ucs_sequence.begin(), ucs_sequence.end());

    // Convert positions back to actual values in B
    vector<int> res;
    unordered_map<int, queue<int>> val_to_pos;
    for (int i = 0; i < M; ++i)
        val_to_pos[B[i]].push(i);

    for (int a : A) {
        if (!ucs_sequence.empty() && !val_to_pos[a].empty() && val_to_pos[a].front() + 1 == ucs_sequence[0]) {
            res.push_back(a);
            ucs_sequence.erase(ucs_sequence.begin());
        }
    }

    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