Submission #1229836

#	Time	Username	Problem	Language	Result	Execution time	Memory
1229836		msrivera1404	Hieroglyphs (IOI24_hieroglyphs)	C++20	29 / 100	57 ms	19904 KiB

hieroglyphs

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

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