Submission #1232710

#	Time	Username	Problem	Language	Result	Execution time	Memory
1232710		MuhammadSaram	Hieroglyphs (IOI24_hieroglyphs)	C++20	0 / 100	1177 ms	1771376 KiB

hieroglyphs

#include "hieroglyphs.h"
#include <bits/extc++.h>

using namespace std;
using namespace __gnu_pbds;

#define all(v) v.begin(), v.end()

vector<int> comb(vector<int> a,vector<int> b)
{
	for (int i:b) a.push_back(i);
	return a;
}

vector<int> solve(int* A,int* B,int l,int r,int l1,int r1)
{
	int n=r-l,m=r1-l1;
	if (n<=0 or m<=0) return {};
	auto a=A+l;
	auto b=B+l1;
	cc_hash_table<int,pair<int,int>> ind,ind1;
	for (int i=0;i<n;i++)
	{
		if (ind.find(a[i])==ind.end()) ind[a[i]]={i,i};
		ind[a[i]].second=i;
	}
	for (int i=0;i<m;i++)
	{
		if (ind1.find(b[i])==ind1.end()) ind1[b[i]]={i,i};
		ind1[b[i]].second=i;
	}
	if (min(n,m)==n)
	{
		if (n==1)
		{
			if (ind1.find(a[0])!=ind1.end()) return {a[0]};
			else return {};
		}
		int mid=n/2;
		for (int i=0;i<=mid;i++)
		{
			if (ind1.find(a[mid-i])!=ind1.end())
			{
				int x=a[mid-i];
				return comb(solve(A,B,l,ind[x].second,l1,ind1[x].second),
				comb({x},solve(A,B,ind[x].first+1,r,ind1[x].first+1,r1)));
			}
			if (mid+i<n && ind1.find(a[mid+i])!=ind1.end())
			{
				int x=a[mid+i];
				return comb(solve(A,B,l,ind[x].second,l1,ind1[x].second),
				comb({x},solve(A,B,ind[x].first+1,r,ind1[x].first+1,r1)));
			}
		}
		return {};
	}
	if (m==1)
	{
		if (ind.find(b[0])!=ind.end()) return {b[0]};
		else return {};
	}
	int mid=m/2;
	for (int i=0;i<=mid;i++)
	{
		if (ind.find(b[mid-i])!=ind.end())
		{
			int x=b[mid-i];
			return comb(solve(A,B,l,ind[x].second,l1,ind1[x].second),
			comb({x},solve(A,B,ind[x].first+1,r,ind1[x].first+1,r1)));
		}
		if (mid+i<m && ind.find(b[mid+i])!=ind.end())
		{
			int x=b[mid+i];
			return comb(solve(A,B,l,ind[x].second,l1,ind1[x].second),
			comb({x},solve(A,B,ind[x].first+1,r,ind1[x].first+1,r1)));
		}
	}
	return {};
}

vector<int> ucs(vector<int> a, vector<int> b)
{
	int n=a.size(),m=b.size();
	int a1[n],b1[m];
	for (int i=0;i<n;i++) a1[i]=a[i];
	for (int i=0;i<m;i++) b1[i]=b[i];
	vector<int> v=solve(a1,b1,0,n,0,m);
	unordered_map<int,vector<int>> ind,ind1;
	for (int i=0;i<n;i++) ind[a[i]].push_back(i);
	for (int i=0;i<m;i++) ind1[b[i]].push_back(i);
	int pre=-1;
	for (int i=0;i<(int)v.size();i++)
	{
		if (!ind.count(v[i])) return {-1};
		auto x=upper_bound(all(ind[v[i]]),pre);
		if (x!=ind[v[i]].end())
			pre=*x;
		else
			return {-1};
	}
	pre=-1;
	for (int i=0;i<(int)v.size();i++)
	{
		if (!ind1.count(v[i])) return {-1};
		auto x=upper_bound(all(ind1[v[i]]),pre);
		if (x!=ind1[v[i]].end())
			pre=*x;
		else
			return {-1};
	}
	return v;
}

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