#include "hieroglyphs.h"
#include <vector>
#include <map>
#include <queue>
using namespace std;
std::vector<int> ucs(std::vector<int> A, std::vector<int> B) {
if (A.size() < B.size()) {
swap(A, B);
}
int ones_A = 0, zeros_A = 0;
int ones_B = 0, zeros_B = 0;
for (int x : A) {
if (x == 0) {
zeros_A++;
} else {
ones_A++;
}
}
for (int x : B) {
if (x == 0) {
zeros_B++;
} else {
ones_B++;
}
}
queue <int> backlog[2][2];
// 0 for A, 1 for B
// 0 for 0, 1 for 1
auto pop_from_backlog = [&](int is_A, int is_zero) -> bool{
if (backlog[is_A][is_zero].size() > 0) {
int found = backlog[is_A][is_zero].front();
backlog[is_A][is_zero].pop();
while (!backlog[is_A][!is_zero].empty()) {
int other = backlog[is_A][!is_zero].front();
if (other < found) {
backlog[is_A][!is_zero].pop();
} else {
break;
}
}
backlog[!is_A][0] = queue <int>();
backlog[!is_A][1] = queue <int>();
return true;
} else {
return false;
}
};
vector <int> seq;
int bad = false;
for (int i = 0; i < A.size(); i++) {
if (i < A.size() - 1 && A[i] != A[i + 1]) {
// 0 1 or 1 0 case
if (i < B.size() - 1 && B[i] != B[i + 1] && B[i] != A[i]) {
// 0 1
// 1 0
// case or vice versa
bad = true;
break;
}
}
if (i < A.size()) {
// has to be mapped, map it to backlog
if (!pop_from_backlog(1, A[i])) {
// put it in backlog, hope for the best
backlog[0][A[i]].push(i);
} else {
seq.push_back(A[i]);
}
}
if (i < B.size()) {
// has to be mapped, map it to backlog
if (!pop_from_backlog(0, B[i])) {
// put it in backlog, hope for the best
backlog[1][B[i]].push(i);
} else {
seq.push_back(B[i]);
}
}
}
if (bad || seq.size() < min(zeros_A, zeros_B) + min(ones_A, ones_B)) {
return vector<int>({-1});
} else {
return seq;
}
}
