Submission #1541872

---

Source Code Expand

#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <vector>
#include <cstring>
#include <queue>
#include <functional>
#include <map>
#include <set>
#define SIZE 2005

using namespace std;
typedef long long int ll;
typedef pair <int,int> P;

char A[SIZE],B[SIZE];
int right[SIZE],left[SIZE];

int solve()
{
	int n=strlen(A);
	vector <int> vx;
	for(int i=0;i<n;i++) if(B[i]=='1') vx.push_back(i);
	for(int i=0;i<n;i++) if(B[i]=='1') vx.push_back(i+n);
	int pos=vx.size()-1;
	for(int i=n-1;i>=0;i--)
	{
		while(pos>0&&vx[pos-1]>=i) pos--;
		right[i]=vx[pos]-i;
	}
	vx.clear();
	for(int i=0;i<n;i++) if(B[i]=='1') vx.push_back(i-n);
	for(int i=0;i<n;i++) if(B[i]=='1') vx.push_back(i);
	pos=0;
	for(int i=0;i<n;i++)
	{
		while(pos+1<vx.size()&&vx[pos+1]<=i) pos++;
		left[i]=i-vx[pos];
	}
	//for(int i=0;i<n;i++) printf("%d %d\n",left[i],right[i]);
	//puts("");
	int ret=n*1000;
	for(int i=0;i<=n;i++)
	{
		int cnt=0;
		vector <P> rg;
		for(int j=0;j<n;j++)
		{
			int to=(i+j)%n;
			if(B[to]!=A[j])
			{
				cnt++;
				rg.push_back(P(right[j],left[j]));
			}
		}
		if(cnt==0)
		{
			ret=min(ret,i);
			continue;
		}
		sort(rg.begin(),rg.end());
		int mx=0,pos=rg.size()-1;
		for(int j=n;j>=i;j--)
		{
			while(pos>=0&&rg[pos].first>j)
			{
				mx=max(mx,rg[pos].second);
				pos--;
			}
			ret=min(ret,(mx+j)*2-i+cnt);
		}
	}
	return ret;
}
int main()
{
	scanf("%s",&A);
	scanf("%s",&B);
	int n=strlen(A);
	bool up=true;
	for(int i=0;i<n;i++) if(B[i]=='1') up=false;
	if(up)
	{
		up=true;
		for(int i=0;i<n;i++) if(A[i]=='1') up=false;
		if(up) puts("0");
		else puts("-1");
		return 0;
	}
	int ret=solve();
	for(int l=0,r=n-1;l<r;l++,r--) swap(A[l],A[r]),swap(B[l],B[r]);
	ret=min(ret,solve());
	printf("%d\n",ret);
	return 0;
}

Submission Info

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:77:15: warning: format ‘%s’ expects argument of type ‘char*’, but argument 2 has type ‘char (*)[2005]’ [-Wformat=]
  scanf("%s",&A);
               ^
./Main.cpp:78:15: warning: format ‘%s’ expects argument of type ‘char*’, but argument 2 has type ‘char (*)[2005]’ [-Wformat=]
  scanf("%s",&B);
               ^
./Main.cpp:77:16: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
  scanf("%s",&A);
                ^
./Main.cpp:78:16: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
  scanf("%s",&B);
                ^

Judge Result