#include "hieroglyphs.h"
#include <bits/stdc++.h>
using namespace std;
const int MAX_SEQ_LEN = 1e5 + 5;
const int MAX_VALUE = 2e5 + 5;
vector<int> posiciones_en_A[MAX_VALUE];
vector<int> posiciones_en_B[MAX_VALUE];
int N_actual, M_actual;
int conteo_en_candidato_UCS[MAX_VALUE];
bool es_A_debil[MAX_VALUE];
bool es_B_debil[MAX_VALUE];
bool puede_seguir(int valor_actual, int ocurrencia_actual, int valor_siguiente, int ocurrencia_siguiente_desde_fin) {
int idx_A_actual = posiciones_en_A[valor_actual][ocurrencia_actual - 1];
int idx_B_actual = posiciones_en_B[valor_actual][ocurrencia_actual - 1];
int idx_A_siguiente = posiciones_en_A[valor_siguiente][posiciones_en_A[valor_siguiente].size() - ocurrencia_siguiente_desde_fin];
int idx_B_siguiente = posiciones_en_B[valor_siguiente][posiciones_en_B[valor_siguiente].size() - ocurrencia_siguiente_desde_fin];
return (idx_A_actual < idx_A_siguiente && idx_B_actual < idx_B_siguiente);
}
std::vector<int> ucs(std::vector<int> A_original, std::vector<int> B_original) {
for(int i = 0; i < MAX_VALUE; ++i) {
posiciones_en_A[i].clear();
posiciones_en_B[i].clear();
conteo_en_candidato_UCS[i] = 0;
es_A_debil[i] = false;
es_B_debil[i] = false;
}
N_actual = A_original.size();
M_actual = B_original.size();
for (int i = 0; i < N_actual; i++) {
posiciones_en_A[A_original[i]].push_back(i);
}
for (int i = 0; i < M_actual; i++) {
posiciones_en_B[B_original[i]].push_back(i);
}
for (int val = 0; val < MAX_VALUE; val++) {
if (posiciones_en_A[val].empty() || posiciones_en_B[val].empty()) {
continue;
}
if (posiciones_en_A[val].size() <= posiciones_en_B[val].size()) {
es_A_debil[val] = true;
} else {
es_B_debil[val] = true;
}
}
vector<int> indices_A_debil;
vector<int> indices_B_debil;
for (int i = 0; i < N_actual; i++) {
if (es_A_debil[A_original[i]]) {
indices_A_debil.push_back(i);
}
}
for (int i = 0; i < M_actual; i++) {
if (es_B_debil[B_original[i]]) {
indices_B_debil.push_back(i);
}
}
vector<int> ucs_candidato_resultante;
int ptr_A_debil = 0;
int ptr_B_debil = 0;
while (ptr_A_debil < indices_A_debil.size() || ptr_B_debil < indices_B_debil.size()) {
int val_A_actual = -1;
int val_B_actual = -1;
if (ptr_A_debil < indices_A_debil.size()) {
val_A_actual = A_original[indices_A_debil[ptr_A_debil]];
}
if (ptr_B_debil < indices_B_debil.size()) {
val_B_actual = B_original[indices_B_debil[ptr_B_debil]];
}
if (val_B_actual == -1) {
ucs_candidato_resultante.push_back(val_A_actual);
conteo_en_candidato_UCS[val_A_actual]++;
ptr_A_debil++;
continue;
}
if (val_A_actual == -1) {
ucs_candidato_resultante.push_back(val_B_actual);
conteo_en_candidato_UCS[val_B_actual]++;
ptr_B_debil++;
continue;
}
bool posible_A_primero = puede_seguir(val_A_actual, 1 + conteo_en_candidato_UCS[val_A_actual], val_B_actual, posiciones_en_B[val_B_actual].size() - conteo_en_candidato_UCS[val_B_actual]);
bool posible_B_primero = puede_seguir(val_B_actual, 1 + conteo_en_candidato_UCS[val_B_actual], val_A_actual, posiciones_en_A[val_A_actual].size() - conteo_en_candidato_UCS[val_A_actual]);
if (posible_A_primero && posible_B_primero) {
return {-1};
} else if (posible_A_primero) {
ucs_candidato_resultante.push_back(val_A_actual);
conteo_en_candidato_UCS[val_A_actual]++;
ptr_A_debil++;
} else {
ucs_candidato_resultante.push_back(val_B_actual);
conteo_en_candidato_UCS[val_B_actual]++;
ptr_B_debil++;
}
}
int ptr_ucs = 0;
for (int i = 0; i < N_actual && ptr_ucs < ucs_candidato_resultante.size(); i++) {
if (A_original[i] == ucs_candidato_resultante[ptr_ucs]) {
ptr_ucs++;
}
}
if (ptr_ucs < ucs_candidato_resultante.size()) {
return {-1};
}
ptr_ucs = 0;
for (int i = 0; i < M_actual && ptr_ucs < ucs_candidato_resultante.size(); i++) {
if (B_original[i] == ucs_candidato_resultante[ptr_ucs]) {
ptr_ucs++;
}
}
if (ptr_ucs < ucs_candidato_resultante.size()) {
return {-1};
}
return ucs_candidato_resultante;
}
