Submission #1254958

#	Time	Username	Problem	Language	Result	Execution time	Memory
1254958		MMihalev	Hieroglyphs (IOI24_hieroglyphs)	C++20	3 / 100	27 ms	7488 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,nA,nB;
vector<int>solve18()
{
    memset(used,0,sizeof(used));
    memset(one,0,sizeof(one));
    memset(used2,0,sizeof(used2));
    emp.clear();minus1.clear();
    minus1.push_back(-1);
    for(int i=1;i<=A.size();i++)
    {
        int x=A[i-1];
        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;

    nA.clear();nB.clear();
    for(int i=1;i<=A.size();i++)
    {
        int x=A[i-1];
        if(used2[x] && used[x])nA.push_back(x);
    }
    for(int i=1;i<=B.size();i++)
    {
        int x=B[i-1];
        if(used[x] && used2[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;
        }
    }
    memset(used,0,sizeof(used));
    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;
        }
    }

    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(s.size() && ra[s.back()]>ra[x])
        {
            if(ra[x]<la[s.back()])return minus1;
            for(int xx:s)
            {
                one[la[xx]]=1;
            }
            if(la[x]<la[s.back()])
            {
                s.clear();
                one[ra[x]]=1;
                continue;
            }
            s.clear();
        }
        if(s.size() && la[x]<la[s.back()])
        {
            one[ra[x]]=1;
            continue;
        }
        if(la[x]<ra[x])s.push_back(x);
    }

    int idleft=-1,idright=s.size();
    for(int i=A.size();i>=1;i--)
    {
        if(!one[i])continue;

        int idxl=0,idxr=s.size()-1,l=0,r=s.size()-1;
        while(l<=r)
        {
            int mid=(l+r)/2;
            if(ra[s[mid]]<i)
            {
                idxl=mid+1;
                l=mid+1;
            }
            else r=mid-1;
        }
        l=0;r=s.size()-1;
        while(l<=r)
        {
            int mid=(l+r)/2;
            if(i<la[s[mid]])
            {
                idxr=mid-1;
                r=mid-1;
            }
            else l=mid+1;
        }

        if(idxr<0 or idxl>=s.size() or !(la[s[idxl]]<=i && i<=ra[s[idxl]]) or !(la[s[idxr]]<=i && i<=ra[s[idxr]]))
        {
            idxl=-1;idxr=-2;
        }

        int lastright=s.size();
        l=idxl;r=idxr;
        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())
        {
            idright=min(idright,lastright);
        }

        int firstleft=min(idxr,lastright-1);

        if(firstleft>=idxl)
        {
            if(lb[A[i-1]]<=lb[s[firstleft]] && lb[s[firstleft]]<=rb[A[i-1]])
            {
                return minus1;
            }
            idleft=max(idleft,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();
    if(ans==emp)return emp;
    //swap(A,nA);swap(B,nB);
    swap(A,B);
    vector<int>ans2=solve18();
    if(ans==ans2)return ans;
    return minus1;
}

• 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