제출 #1229816

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1229816		msrivera1404	상형문자열 (IOI24_hieroglyphs)	C++20	0 / 100	93 ms	5008 KiB

hieroglyphs

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

    std::vector<std::vector<int>> pos_A_mid(2); 
    std::vector<std::vector<int>> pos_B_mid(2);

    for (int i = 0; i < A_middle.size(); ++i) {
        pos_A_mid[A_middle[i]].push_back(i);
    }
    for (int i = 0; i < B_middle.size(); ++i) {
        pos_B_mid[B_middle[i]].push_back(i);
    }

    int ptr_a = 0; 
    int ptr_b = 0; 

    while (ptr_a < A_middle.size() || ptr_b < B_middle.size()) { 
        int val_a = -1, val_b = -1; 

        if (ptr_a < A_middle.size()) {
            val_a = A_middle[ptr_a];
        }
        if (ptr_b < B_middle.size()) {
            val_b = B_middle[ptr_b];
        }

        if (val_a != -1 && val_b != -1 && val_a == val_b) {
            ucs_middle_candidate.push_back(val_a);
            ptr_a++;
            ptr_b++;
        } else {
            bool can_take_val_a_from_A = false;
            if (val_a != -1) {
                auto it_b_for_val_a = std::lower_bound(pos_B_mid[val_a].begin(), pos_B_mid[val_a].end(), ptr_b);
                if (it_b_for_val_a != pos_B_mid[val_a].end()) {
                    can_take_val_a_from_A = true;
                }
            }
            bool can_take_val_b_from_B = false;
            if (val_b != -1) {
                auto it_a_for_val_b = std::lower_bound(pos_A_mid[val_b].begin(), pos_A_mid[val_b].end(), ptr_a);
                if (it_a_for_val_b != pos_A_mid[val_b].end()) {
                    can_take_val_b_from_B = true;
                }
            }
            
            if (can_take_val_a_from_A && can_take_val_b_from_B) {
                return {-1}; 
            } else if (can_take_val_a_from_A) {
                ucs_middle_candidate.push_back(val_a);
                ptr_a++;
            } else if (can_take_val_b_from_B) {
                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;
}

• Subtask 0: 0 / 0
• Subtask 1: 0 / 3
• Subtask 2: 0 / 15
• Subtask 3: 0 / 10
• Subtask 4: 0 / 16
• Subtask 5: 0 / 14
• Subtask 6: 0 / 42