| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1255450 | MMihalev | Hieroglyphs (IOI24_hieroglyphs) | C++20 | 0 ms | 0 KiB |
#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(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;
}