Submission #1366955

#TimeUsernameProblemLanguageResultExecution timeMemory
1366955ivazivaNecklace (Subtask 1-3) (BOI19_necklace1)C++20
0 / 85
7 ms412 KiB
#include <bits/stdc++.h>

using namespace std;

#define MAXN 3005
#define int long long 

int n1,n2;string s1,s2;
set<pair<char,pair<char,char>>> edges;
set<pair<char,pair<char,char>>> copied;

int32_t main()
{
	cin>>s1>>s2;n1=(int)s1.size();n2=(int)s2.size();
	int answer=INT_MAX,pos1=-1,pos2=-1;
	for (int i=0;i<n1;i++)
	{
		for (int j=0;j<n2;j++)
		{
			if (s1[i]==s2[j]) {answer=max(n1,n2)-1;pos1=i;pos2=j;}
		}
	}
	for (int len=2;len<=min(n1,n2);len++)
	{
		for (int i=0;i+len-1<=n1-1;i++)
		{
			for (int pos=i;pos<=i+len-1;pos++)
			{
				if (pos==i) {edges.insert({s1[i],{s1[i+len-1],s1[i+1]}});continue;}
				if (pos==i+len-1) {edges.insert({s1[i+len-1],{s1[i+len-2],s1[i]}});continue;}
				edges.insert({s1[pos],{s1[pos-1],s1[pos+1]}});
			}
			for (int j=0;j+len-1<=n2-1;j++)
			{
				copied=edges;bool valid=true;
				for (int pos=j;pos<=j+len-1;pos++)
				{
					if (pos==j)
					{
						if (edges.find({s2[j],{s2[j+len-1],s2[j+1]}})!=edges.end()) {edges.erase({s2[j],{s2[j+len-1],s2[j+1]}});continue;}
						if (edges.find({s2[j],{s2[j+1],s2[j+len-1]}})!=edges.end()) {edges.erase({s2[j],{s2[j+1],s2[j+len-1]}});continue;}
						valid=false;break;
					}
					if (pos==j+len-1)
					{
						if (edges.find({s2[j+len-1],{s2[j+len-2],s2[j]}})!=edges.end()) {edges.erase({s2[j+len-1],{s2[j+len-2],s2[j]}});continue;}
						if (edges.find({s2[j+len-1],{s2[j],s2[j+len-2]}})!=edges.end()) {edges.erase({s2[j+len-1],{s2[j],s2[j+len-2]}});continue;}
						valid=false;break;
					}
					if (edges.find({s2[pos],{s2[pos-1],s2[pos+1]}})!=edges.end()) {edges.erase({s2[pos],{s2[pos-1],s2[pos+1]}});continue;}
					if (edges.find({s2[pos],{s2[pos+1],s2[pos-1]}})!=edges.end()) {edges.erase({s2[pos],{s2[pos+1],s2[pos-1]}});continue;}
					valid=false;break;
				}
				if (valid) 
				{
					if (max(n1,n2)-len<answer) {answer=max(n1,n2)-len;pos1=i;pos2=j;}
			    }
		    }
		    edges.clear();copied.clear();
		}
	}
	cout<<answer<<endl;
	cout<<pos1<<" "<<pos2<<endl;
}
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...