Submission #2008503

---

Source Code Expand

#include <bits/stdc++.h>

using std::min;

const int N=2010;

int n,pre[N],lst[N],l[N],r[N];
bool can[N<<1];
char A[N<<1],B[N];

void Init() {
	scanf("%s%s",A,B);
	n=strlen(A);
}

void Solve() {
	int ans=n*n+1,fir=n*n+1000,end=n*n+1000;
	for (int i=0;i<n;++i) if (B[i]=='1') { fir=i; break; }
	for (int i=n-1;i>=0;--i) if (B[i]=='1') { end=i; break; }
	for (int i=0;i<n;++i) if (B[i]=='1') pre[i]=i;else pre[i]=i?pre[i-1]:end-n;
	for (int i=n-1;i>=0;--i)  if (B[i]=='1') lst[i]=i;else lst[i]=i<n-1?lst[i+1]:fir+n;
	
	for (int i=0;i<n;++i) A[i+n]=A[i],l[i]=n+1,r[i]=n+1;
	for (int p=0;p<=n;++p) {
		int cnt=0,movl=0,movr=0;
		for (int j=n-1;j>=0;--j) {
			if (B[j]=='1') can[(j+p)%n]=1;
			else l[(j+p)%n]=min(l[(j+p)%n],j-pre[j]),r[(j+p)%n]=min(r[(j+p)%n],lst[j]-j);
			if (A[j+p]!=B[j] && cnt!=-1) {
				if (can[(j+p)%n]) cnt++;
				else if ((l[(j+p)%n]<=n && l[(j+p)%n]>=0) || (r[(j+p)%n]<=n && r[(j+p)%n]>=0)) {
					int d1=r[(j+p)%n],d2=l[(j+p)%n];
					cnt++;
					if (d1<=movr || d2<=movl) continue;
					else if (d1<d2) movr=d1;else movl=d2;
				}
				else cnt=n*n+1;
			}
		}
		ans=min(ans,cnt+p+movr*2+movl*2);
	}
	for (int i=0;i<n;++i) l[i]=n+1,r[i]=n+1;
	for (int i=0;i<n*2;++i) can[i]=0;
	for (int p=n;p>=0;--p) {
		int cnt=0,movr=0,movl=0;
		for (int j=0;j<n;++j) {
			if (B[j]=='1') can[(j+p)%n]=1;
			else l[(j+p)%n]=min(l[(j+p)%n],j-pre[j]),r[(j+p)%n]=min(r[(j+p)%n],lst[j]-j);
			if (A[j+p]!=B[j] && cnt!=-1) {
				if (can[(j+p)%n]) cnt++;
				else if ((l[(j+p)%n]<=n && l[(j+p)%n]>=0) || (r[(j+p)%n]<=n && r[(j+p)%n]>=0)) {
					int d1=r[(j+p)%n],d2=l[(j+p)%n];
					cnt++;
					if (d1<=movr || d2<=movl) continue;
					else if (d1<d2) movr=d1;else movl=d2;
				}
				else cnt=n*n+1;
			}
		}
		ans=min(ans,cnt+n-p+movr*2+movl*2);
	}
	if (ans==n*n+1) printf("-1\n");
	else printf("%d\n",ans);
}

int main() {
	Init();
	Solve();
	return 0;
}

Submission Info

Compile Error

./Main.cpp: In function ‘void Init()’:
./Main.cpp:12:19: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
  scanf("%s%s",A,B);
                   ^

Judge Result