Submission #1229637

#TimeUsernameProblemLanguageResultExecution timeMemory
1229637msrivera1404Hieroglyphs (IOI24_hieroglyphs)C++20
3 / 100
1096 ms3828 KiB
#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 timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...