Submission #1254903

#	Time	Username	Problem	Language	Result	Execution time	Memory
1254903		MMihalev	Hieroglyphs (IOI24_hieroglyphs)	C++20	3 / 100	24 ms	6976 KiB

hieroglyphs

#include<iostream>
#include <vector>
#include<cstring>
#include "hieroglyphs.h"
using namespace std;
const int MAX_N=2e5+5;
bool used[MAX_N],used2[MAX_N];
int la[MAX_N],ra[MAX_N];
int lb[MAX_N],rb[MAX_N];
bool one[MAX_N];
vector<int>emp,minus1;
vector<int>A,B;
vector<int>solve18()
{
    emp.clear();
    minus1.push_back(-1);

    for(int i=1;i<=A.size();i++)
    {
        int x=A[i-1];

        if(used[x])
        {
            ra[x]=i;
        }
        else
        {
            la[x]=i;
            ra[x]=i;
            used[x]=1;
        }
    }
    int cnt=0;
    for(int i=1;i<=B.size();i++)
    {
        int x=B[i-1];
        used2[x]=1;
        if(!used[x])cnt++;
    }
    if(cnt==B.size())return emp;

    vector<int>nA,nB;
    for(int i=1;i<=A.size();i++)
    {
        int x=A[i-1];
        if(used2[x])nA.push_back(x);
    }
    for(int i=1;i<=B.size();i++)
    {
        int x=B[i-1];
        if(used[x])nB.push_back(x);
    }
    swap(A,nA);swap(B,nB);

    memset(used,0,sizeof(used));
    for(int i=1;i<=B.size();i++)
    {
        int x=B[i-1];
        if(used[x])
        {
            rb[x]=i;
        }
        else
        {
            lb[x]=i;
            rb[x]=i;
            used[x]=1;
        }
    }

    vector<int>order;
    for(int i=1;i<=A.size();i++)
    {
        int x=A[i-1];
        if(la[x]==ra[x])
        {
            one[i]=1;
        }
    }
    for(int i=1;i<=B.size();i++)
    {
        int x=B[i-1];
        if(lb[x]==rb[x])
        {
            order.push_back(x);
        }
    }

    vector<int>s;
    for(int x:order)
    {
        if(la[x]==ra[x])continue;

        if(s.size() && ra[s.back()]>ra[x])
        {
            if(ra[x]<la[s.back()])return minus1;
            for(int xx:s)
            {
                one[la[xx]]=1;
            }
            s.clear();
        }
        if(s.size() && la[x]<la[s.back()])
        {
            one[ra[x]]=1;
            continue;
        }
        s.push_back(x);
    }
    int idxl=s.size(),idxr=s.size();
    int idleft=-1,idright=s.size();
    for(int i=A.size();i>=1;i--)
    {
        while((idxr>=0 && idxr<s.size() && (!(la[s[idxr]]<=i && i<=ra[s[idxr]]))) or (idxr>0 && idxr==s.size() && (i<=ra[s[idxr-1]])))idxr--;
        while(idxl>0 && (la[s[idxl-1]]<=i && i<=ra[s[idxl-1]]))idxl--;

        if(!one[i])continue;

        int lastright=s.size();
        int l=0,r=s.size()-1;
        while(l<=r)
        {
            int mid=(l+r)/2;
            if(lb[s[mid]]>rb[A[i-1]])
            {
                lastright=mid;
                r=mid-1;
            }
            else l=mid+1;
        }

        if(lastright<s.size())
        {
            if(lastright<=idxr)
            {
                idright=min(idright,max(idxl,lastright));
            }
        }

        int firstleft=lastright-1;
        if(firstleft>=0)
        {
            if(lb[A[i-1]]<=lb[s[firstleft]] && lb[s[firstleft]]<=rb[A[i-1]])return minus1;
            if(firstleft>=idxl)
            {
                idleft=max(idleft,min(idxr,firstleft));
            }
        }
    }

    if(idleft>=idright)return minus1;

    for(int i=0;i<=idleft;i++)
    {
        one[la[s[i]]]=1;
    }
    for(int i=idright;i<s.size();i++)
    {
        one[ra[s[i]]]=1;
    }

    for(int i=idleft+1;i<idright;i++)
    {
        one[la[s[i]]]=1;
    }

    vector<int>u;
    for(int i=1;i<=A.size();i++)
    {
        if(one[i])u.push_back(A[i-1]);
    }
    int pos=0;
    for(int i=1;i<=B.size();i++)
    {
        if(pos<u.size() && B[i-1]==u[pos])pos++;
    }
    if(pos==u.size() && pos)return u;
    return minus1;
}
std::vector<int> ucs(std::vector<int> a, std::vector<int> b)
{
    A=a;
    B=b;
    vector<int>ans=solve18();
    return ans;
}

• 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