#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};
}
}
