Submission #1255521

#	Time	Username	Problem	Language	Result	Execution time	Memory
1255521		MMihalev	Hieroglyphs (IOI24_hieroglyphs)	C++20	18 / 100	45 ms	10084 KiB

hieroglyphs

#include<iostream>
#include<vector>
#include<cstring>
#include<set>
#include<algorithm>
#include "hieroglyphs.h"
using namespace std;
const int MAX_N=3e5+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];
int cnt3[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<pair<int,int>>intervals;
    set<pair<int,int>>intervalsleft;
    set<pair<int,int>>points;
    for(int i=1;i<=A.size();i++)
    {
        int x=A[i-1];
        if(la[x]<ra[x] && la[x]==i)
        {
            intervals.push_back({ra[x],x});
        }
    }
    sort(intervals.begin(),intervals.end());
    int idx=intervals.size();
    for(int i=A.size();i>=1;i--)
    {
        int x=A[i-1];
        if(la[x]!=ra[x])continue;
        while(idx-1>=0 && intervals[idx-1].first>=i)
        {
            if(la[intervals[idx-1].second]<=i)
            {
                points.insert({lb[intervals[idx-1].second],intervals[idx-1].second});
                intervalsleft.insert({la[intervals[idx-1].second],intervals[idx-1].second});
            }
            idx--;
        }
        while(intervalsleft.size())
        {
            auto top=(*(intervalsleft.rbegin()));
            if(top.first>i)
            {
                points.erase({lb[top.second],top.second});
                intervalsleft.erase(top);
            }
            else break;
        }
        auto it=points.upper_bound({lb[x],-1});
        if(it==points.end())continue;
        auto middle=(*(it));
        if(lb[middle.second]<rb[x])return minus1;
    }


    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 && la[x]<ra[x])
            {
                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;
        curs.push_back(s[0]);
        for(int i=1;i<s.size();i++)
        {
            if(!(la[s[i]]<ra[s[i-1]]))
            {
                ss.push_back(curs);
                curs.clear();
            }
            curs.push_back(s[i]);
        }
        ss.push_back(curs);
    }

    for(auto s2:ss)
    {
        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(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;
    }
    ///solve3


    memset(cnt3,0,sizeof(cnt3));
    ma=0;
    for(int x:A)
    {
        cnt3[x]++;
        ma=max(ma,cnt3[x]);
    }
    for(int x:B)
    {
        cnt3[x]++;
        ma=max(ma,cnt3[x]);
    }
    if(ma<=3)return solve18();
    ///solve15
}

Compilation message (stderr)

hieroglyphs.cpp: In function 'std::vector<int> ucs(std::vector<int>, std::vector<int>)':
hieroglyphs.cpp:349:1: warning: control reaches end of non-void function [-Wreturn-type]
  349 | }
      | ^

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