Submission #1229836

#TimeUsernameProblemLanguageResultExecution timeMemory
1229836msrivera1404상형문자열 (IOI24_hieroglyphs)C++20
29 / 100
57 ms19904 KiB
#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; }
#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...