Submission #2008836

---

Source Code Expand

#include <bits/stdc++.h>

using std::min;
using std::pair;
using std::make_pair;

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);
}

pair<int,int>pt[N];
int check(int n,int movr) {
	int val=0;
	for (int i=1;i<=n;++i) {
		pair<int,int> u=pt[i];
		if (u.first>movr && val<u.second) val=u.second;
	}
	return val;
}

void Solve() {
	int ans=n*n+1000,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,top=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]) {
				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++;
					pt[++top]=make_pair(d1,d2);
				}
				else cnt=n*n+1000;
			}
		}
		int l=0,r=n,bst=check(top,n)+n;
		while (l<=r) {
			int mid=(l+r)>>1,val=check(top,mid)+mid;
			if (bst>val) bst=val,r=mid-1;
			else l=mid+1;
		}
		bst=check(top,l)+l;
		ans=min(ans,cnt+p+bst*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,top=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]) {
				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++;
					pt[++top]=make_pair(d1,d2);
				}
				else cnt=n*n+1000;
			}
		}
		int l=0,r=n,bst=check(top,n)+n;
		while (l<=r) {
			int mid=(l+r)>>1,val=check(top,mid)+mid;
			if (bst>val) bst=val,r=mid-1;
			else l=mid+1;
		}
		bst=check(top,l)+l;
		ans=min(ans,cnt+n-p+bst*2);
	}
	if (ans==n*n+1000) 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:14: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