Submission #1313103

#	Time	Username	Problem	Language	Result	Execution time	Memory
1313103		eri16	Hieroglyphs (IOI24_hieroglyphs)	C++20	3 / 100	21 ms	2324 KiB

hieroglyphs

#include<bits/stdc++.h>
#include "hieroglyphs.h"

using namespace std;

bool contains(const vector<int>& big, const vector<int>& small){
    if (small.size()>big.size()) return false;

    int n=big.size(), m=small.size();
    vector<int> lps(m, 0);

    for (int i=1, len=0; i<m;){
        if (small[i]==small[len]){lps[i++]=++len;} 
        else if (len!=0){len=lps[len-1];} 
        else{lps[i++]=0;}
    }
    
    for (int i=0, j=0; i<n;){
        if (big[i]==small[j]){
            i++; j++;
        }
        if (j==m) return true;
        else if (i<n && big[i]!=small[j]){
            if (j!=0) j=lps[j-1];
            else i++;
        }
    }
    return false;
}

vector<int> ucs(vector<int> A, vector<int> B) {
    if (contains(A, B)) return B;
    if (contains(B, A)) return A;
    return {-1};
}

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