#include <vector> #include <unordered_set> #include <unordered_map> #include <queue> #include <algorithm> using namespace std; vector<int> ucs(vector<int> A, vector<int> B) { const int INF = 1000000000; int n = (int)A.size(); int m = (int)B.size(); // Build sets for A and B unordered_set<int> setA, setB; for (int x : A) setA.insert(x); for (int x : B) setB.insert(x); // common = set(A) & set(B) unordered_set<int> common; for (int x : setA) { if (setB.count(x)) { common.insert(x); } } if (common.empty()) { return {}; } // listB[x] = list of positions of x in B unordered_map<int, vector<int>> listB; for (int x : common) { listB[x] = vector<int>(); // ensure key exists } for (int j = 0; j < m; ++j) { int x = B[j]; if (common.count(x)) { listB[x].push_back(j); } } // count_in_A[x] = occurrences of x in A unordered_map<int, int> count_in_A; for (int a : A) { if (common.count(a)) { count_in_A[a]++; // default 0 then increment } } // available[x] = min(count_in_A[x], len(listB[x])) unordered_map<int, int> available; for (int x : common) { int cntA = count_in_A[x]; int cntB = (int)listB[x].size(); available[x] = min(cntA, cntB); } int L = 0; for (int x : common) { L += available[x]; } if (L == 0) { return {}; } // threshold_arr[x] unordered_map<int, int> threshold_arr; for (int x : common) { if (available[x] > 0) { int index_in_list = (int)listB[x].size() - available[x]; threshold_arr[x] = listB[x][index_in_list]; } else { threshold_arr[x] = INF; } } // min-heap over (threshold, value) using PII = pair<int, int>; priority_queue<PII, vector<PII>, greater<PII>> heap_over_y; for (int x : common) { if (available[x] > 0) { heap_over_y.push({threshold_arr[x], x}); } } int lastB = -1; vector<int> U; for (int i = 0; i < n; ++i) { int x = A[i]; if (!common.count(x) || available[x] <= 0) { continue; } int threshold = INF; if (available[x] > 1) { int future_avail = available[x] - 1; int index_in_list = (int)listB[x].size() - future_avail; int candidate = listB[x][index_in_list]; threshold = candidate; } // Clean the heap top: discard outdated entries or those with y == x while (!heap_over_y.empty()) { PII top = heap_over_y.top(); int th = top.first; int y = top.second; int current_threshold_y = INF; auto it = threshold_arr.find(y); if (it != threshold_arr.end()) { current_threshold_y = it->second; } if (y == x || th != current_threshold_y) { heap_over_y.pop(); } else { break; } } if (!heap_over_y.empty()) { int th = heap_over_y.top().first; if (th < threshold) { threshold = th; } } // pos = bisect_right(listB[x], lastB) vector<int> &positions = listB[x]; auto itPos = upper_bound(positions.begin(), positions.end(), lastB); size_t pos = itPos - positions.begin(); if (pos >= positions.size()) { continue; } bool found = false; int j_candidate = -1; while (pos < positions.size()) { int j = positions[pos]; if (j < threshold) { found = true; j_candidate = j; break; } ++pos; } if (!found) { continue; } U.push_back(x); lastB = j_candidate; available[x] -= 1; if (available[x] == 0) { threshold_arr[x] = INF; } else { int index_in_list = (int)positions.size() - available[x]; int new_threshold = positions[index_in_list]; threshold_arr[x] = new_threshold; heap_over_y.push({new_threshold, x}); } } if ((int)U.size() == L) { return U; } else { return vector<int>{-1}; } }