Submission #1178606

#	Time	Username	Problem	Language	Result	Execution time	Memory
1178606		alexander707070	Hieroglyphs (IOI24_hieroglyphs)	C++20	0 / 100	1082 ms	364732 KiB

hieroglyphs

#include<bits/stdc++.h>
#define MAXN 3007
using namespace std;

int n,m,k,cnt;
int a[MAXN],b[MAXN],c[MAXN];
int dp[MAXN][MAXN];
int nxt[MAXN][2*MAXN],last[2*MAXN];

unordered_map<int,int> mp;
int ret[200007];

void compress(){
	vector<int> vals;

	for(int i=1;i<=n;i++)vals.push_back(a[i]);
	for(int i=1;i<=m;i++)vals.push_back(b[i]);

	sort(vals.begin(),vals.end());

	cnt=0;
	for(int i=0;i<vals.size();i++){
		if(i==0 or vals[i]!=vals[i-1])cnt++;
		mp[vals[i]]=cnt; ret[cnt]=vals[i];
	}

	for(int i=1;i<=n;i++)a[i]=mp[a[i]];
	for(int i=1;i<=m;i++)b[i]=mp[b[i]];
}

void findseq(int l,int r){
	if(dp[l][r]==0)return;

	if(dp[l][r]==dp[l-1][r]){
		findseq(l-1,r);
		return;
	}
	
	if(dp[l][r]==dp[l][r-1]){
		findseq(l,r-1);
		return;
	}

	k++; c[k]=a[l];
	findseq(l-1,r-1);
}


unordered_set<long long> s;

long long state(long long a,long long b,long long c){
	return c+b*10000+a*10000*10000;
}

bool brute(int x,int y,int z){
	if(x==n+1 or y==n+1)return false;

	long long curr=state(x,y,z);
	if(s.find(curr)!=s.end())return false;
	s.insert(curr);

	bool res=false;
	if(a[x]==b[y]){
		if(nxt[z][a[x]]>k)res=true;
		else if(brute(x+1,y+1,nxt[z][a[x]]))res=true;
	}else{
		if(brute(x+1,y,z))res=true;
		else if(brute(x,y+1,z))res=true;
	}

	return res;
}

vector<int> ucs(vector<int> A, vector<int> B){
	n=int(A.size());
	m=int(B.size());

	for(int i=1;i<=n;i++)a[i]=A[i-1];
	for(int i=1;i<=m;i++)b[i]=B[i-1];

	compress();

	for(int i=1;i<=n;i++){
		for(int f=1;f<=m;f++){
			dp[i][f]=max(dp[i-1][f],dp[i][f-1]);

			if(a[i]==b[f])dp[i][f]=max(dp[i][f],dp[i-1][f-1]+1);
		}
	}

	findseq(n,m);
	reverse(c+1,c+k+1);

	for(int i=1;i<=cnt;i++)last[i]=k+1;

	for(int i=k;i>=0;i--){
		for(int f=1;f<=cnt;f++)nxt[i][f]=last[f];
		last[c[i]]=i;
	}

	vector<int> sol;
	if(!brute(1,1,0)){
		for(int i=1;i<=k;i++)sol.push_back(ret[c[i]]);
		return sol;
	}

	return {-1};
}

/*int main(){

	//auto s=ucs({0, 0, 1, 0, 1, 2}, {2, 0, 1, 0, 2});
	auto s=ucs({0, 1, 0}, {1, 0, 1});

	for(int i:s)cout<<i<<" ";

	return 0;
}*/

• 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