Submission #1313108

#	Time	Username	Problem	Language	Result	Execution time	Memory
1313108		eri16	Hieroglyphs (IOI24_hieroglyphs)	C++20	3 / 100	20 ms	2540 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;
    
    int A0=0,A1=0,B0=0,B1=0;
    
    for (int i=0; i<A.size(); i++){if (A[i]==0){A0++;}else{A1++;}}
    for (int i=0; i<B.size(); i++){if (B[i]==0){B0++;}else{B1++;}}    
    
    vector <int> ans;
    
    if (A0==0 || B0==0){
        int lk = min(A1,B1);
        if (lk!=0){
            for (int i=0 ; i<lk; i++){
                ans.push_back(1);
            }
            return ans;
        }
    }
    if (A1==0 || B1==0){
        int lk = min(A0,B0);
        if (lk!=0){
            for (int i=0 ; i<lk; i++){
                ans.push_back(0);
            }
            return ans;
        }
    }    
    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