Submission #1543150

---

Source Code Expand

#include<stdio.h>
#include<vector>
#include<algorithm>
#include<string>
#include<iostream>
using namespace std;
int las[20000],rlas[20000];
typedef pair<int,int>pii;
int solve(string sa,string sb)
{
	int num=sa.size();
	sa=sa+sa+sa+sa+sa,sb=sb+sb+sb+sb+sb;
	for(int i=1;i<sb.size();i++)
	{
		las[i]=las[i-1];
		if(sb[i]=='1')las[i]=i;
	}
	for(int i=sb.size()-2;i>=0;i--)
	{
		rlas[i]=rlas[i+1];
		if(sb[i]=='1')rlas[i]=i;
	}
	int mini=1000000000;
	for(int p=0;p<num;p++)
	{
		vector<pii>v;
		int cnt=0;
		//printf("- %d\n",p);
		for(int i=num+num;i<num+num+num;i++)
		{
			if(sa[i]==sb[i+p])continue;
			pii z=make_pair(0,0);
			if(las[i+p]<i)z.first=i-las[i+p];
			if(rlas[i]>i+p)z.second=rlas[i]-(i+p);
			v.push_back(z);
			cnt++;
			//printf("%d %d %d\n",i-num-num,z.first,z.second);
		}
		sort(v.begin(),v.end());
		reverse(v.begin(),v.end());
		int now=0;
		int mi=1000000000;
		for(int i=0;i<v.size();i++)
		{
			mi=min(mi,(v[i].first+now)*2+cnt+p);
			now=max(now,v[i].second);
		}
		mi=min(mi,now*2+cnt+p);
		mi=min(mi,num+cnt+p);
		//printf(" %d\n",mi);
		mini=min(mini,mi);
	}
	return mini;
}
int main()
{
	string sa,sb;
	cin>>sa>>sb;
	if(sa==sb)
	{
		printf("0\n");
		return 0;
	}
	int cnt=0;
	for(int i=0;i<sb.size();i++)if(sb[i]=='1')cnt++;
	if(cnt==0)
	{
		printf("-1\n");
		return 0;
	}
	int ans1=solve(sa,sb);
	reverse(sa.begin(),sa.end());
	reverse(sb.begin(),sb.end());
	int ans2=solve(sa,sb);
	printf("%d\n",min(ans1,ans2));
}

Submission Info

Judge Result