Submission #1255455

#	Time	Username	Problem	Language	Result	Execution time	Memory
1255455		MMihalev	Hieroglyphs (IOI24_hieroglyphs)	C++20	3 / 100	1092 ms	8832 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;
            }
            bool pushback=1;
            int last=s.back();
            one[la[s.back()]]=1;
            s.pop_back();
            if(la[x]<la[last])
            {
                one[ra[x]]=1;
                pushback=0;
            }
            while(s.size() && ra[s.back()]>la[last])
            {
                last=s.back();
                one[la[last]]=1;
                s.pop_back();
            }
            if(pushback)
            {
                s.push_back(x);
            }
            continue;
        }
        if(s.size() && la[x]<la[s.back()])
        {
            one[ra[x]]=1;
            continue;
        }
        if(la[x]<ra[x])s.push_back(x);
    }

    vector<vector<int>>ss;

    if(s.size())
    {
        vector<int>curs;
        int last=s[0];
        curs.push_back(last);
        for(int i=1;i<s.size();i++)
        {
            if(la[s[i]]<ra[last]);
            else
            {
                ss.push_back(curs);
                curs.clear();
                last=s[i];
            }
            curs.push_back(s[i]);
        }
        ss.push_back(curs);
    }

    for(auto s2:ss)
    {
        if(s2.size()==0)continue;

        int idleft=-1,idright=s2.size();
        int borr=ra[s2.back()],borl=la[s2[0]];
        for(int i=borr;i>=borl;i--)
        {
            if(!one[i])continue;

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

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

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

            if(lastright<s2.size())
            {
                idright=min(idright,lastright);
            }

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

            if(firstleft>=idxl)
            {
                if(rb[A[i-1]]==lb[A[i-1]])while(1);

                if(la[s2[firstleft]]<=la[A[i-1]] && la[A[i-1]]<=ra[s2[firstleft]] && lb[A[i-1]]<=lb[s2[firstleft]] && lb[s2[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[s2[i]]]=1;
        }
        for(int i=idright;i<s2.size();i++)
        {
            one[ra[s2[i]]]=1;
        }

        for(int i=idleft+1;i<idright;i++)
        {
            one[la[s2[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;

    bool permA=1,permB=1;
    int ma=0;
    for(int i=0;i<A.size();i++)
    {
        ma=max(ma,A[i]);
        if(used[A[i]])permA=0;
        used[A[i]]=1;
    }
    memset(used,0,sizeof(used));
    for(int i=0;i<B.size();i++)
    {
        ma=max(ma,B[i]);
        if(used[B[i]])permB=0;
        used[B[i]]=1;
    }
    memset(used,0,sizeof(used));
    if(permA && permB && A.size()==B.size() && ma+1==A.size())
    {
        if(A==B)return A;
        emp.push_back(-1);
        return emp;
    }

    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