#include "hieroglyphs.h"
#include<bits/stdc++.h>
bool is_subsequence(const std::vector<int>& s, const std::vector<int>& t) {
if (s.empty()) {
return true;
}
if (t.empty()) {
return false;
}
int s_ptr = 0;
int t_ptr = 0;
while (s_ptr < s.size() && t_ptr < t.size()) {
if (s[s_ptr] == t[t_ptr]) {
s_ptr++;
}
t_ptr++;
}
return s_ptr == s.size();
}
std::vector<int> get_common_prefix(const std::vector<int>& a, const std::vector<int>& b) {
std::vector<int> common_prefix;
int min_len = std::min(a.size(), b.size());
for (int i = 0; i < min_len; ++i) {
if (a[i] == b[i]) {
common_prefix.push_back(a[i]);
} else {
break;
}
}
return common_prefix;
}
std::vector<int> get_common_suffix(const std::vector<int>& a, const std::vector<int>& b) {
std::vector<int> common_suffix;
int i_a = a.size() - 1;
int i_b = b.size() - 1;
while (i_a >= 0 && i_b >= 0 && a[i_a] == b[i_b]) {
common_suffix.insert(common_suffix.begin(), a[i_a]);
i_a--;
i_b--;
}
return common_suffix;
}
std::pair<bool, int> is_monotone(const std::vector<int>& seq) {
if (seq.empty()) {
return {true, -1};
}
int first_val = seq[0];
for (int x : seq) {
if (x != first_val) {
return {false, -1};
}
}
return {true, first_val};
}
std::vector<int> ucs(std::vector<int> A_orig, std::vector<int> B_orig) {
std::vector<int> ucs_prefix = get_common_prefix(A_orig, B_orig);
std::vector<int> A_prime(A_orig.begin() + ucs_prefix.size(), A_orig.end());
std::vector<int> B_prime(B_orig.begin() + ucs_prefix.size(), B_orig.end());
std::vector<int> ucs_suffix = get_common_suffix(A_prime, B_prime);
std::vector<int> A_middle(A_prime.begin(), A_prime.end() - ucs_suffix.size());
std::vector<int> B_middle(B_prime.begin(), B_prime.end() - ucs_suffix.size());
std::vector<int> ucs_middle_candidate;
int ptr_a = 0;
int ptr_b = 0;
while (ptr_a < A_middle.size() && ptr_b < B_middle.size()) {
int val_a = A_middle[ptr_a];
int val_b = B_middle[ptr_b];
if (val_a == val_b) {
ucs_middle_candidate.push_back(val_a);
ptr_a++;
ptr_b++;
} else {
int next_val_a_in_B = -1;
for(int i = ptr_b; i < B_middle.size(); ++i) {
if (B_middle[i] == val_a) {
next_val_a_in_B = i;
break;
}
}
int next_val_b_in_A = -1;
for(int i = ptr_a; i < A_middle.size(); ++i) {
if (A_middle[i] == val_b) {
next_val_b_in_A = i;
break;
}
}
bool path_a_valid = (next_val_a_in_B != -1);
bool path_b_valid = (next_val_b_in_A != -1);
if (path_a_valid && path_b_valid) {
return {-1};
} else if (path_a_valid) {
ucs_middle_candidate.push_back(val_a);
ptr_a++;
} else if (path_b_valid) {
ucs_middle_candidate.push_back(val_b);
ptr_b++;
} else {
break;
}
}
}
if (!is_subsequence(ucs_middle_candidate, A_middle) || !is_subsequence(ucs_middle_candidate, B_middle)) {
return {-1};
}
std::vector<int> final_ucs;
final_ucs.reserve(ucs_prefix.size() + ucs_middle_candidate.size() + ucs_suffix.size());
final_ucs.insert(final_ucs.end(), ucs_prefix.begin(), ucs_prefix.end());
final_ucs.insert(final_ucs.end(), ucs_middle_candidate.begin(), ucs_middle_candidate.end());
final_ucs.insert(final_ucs.end(), ucs_suffix.begin(), ucs_suffix.end());
return final_ucs;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |