Submission #1612883

---

Source Code Expand

#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<set>
#include<bitset>
#include<map>

#define fo(i,a,b) for(int i=a;i<=b;i++)
#define fd(i,a,b) for(int i=a;i>=b;i--)

using namespace std;

typedef long long LL;
typedef double db;

int get(){
	char ch;
	while(ch=getchar(),(ch<'0'||ch>'9')&&ch!='-');
	if (ch=='-'){
		int s=0;
		while(ch=getchar(),ch>='0'&&ch<='9')s=s*10+ch-'0';
		return -s;
	}
	int s=ch-'0';
	while(ch=getchar(),ch>='0'&&ch<='9')s=s*10+ch-'0';
	return s;
}

const int N = 2003;

int n;
int a[N],b[N];
struct point{
	int x,y;
	friend bool operator < (point a,point b){
		return a.x<b.x;
	}
}p[N];
int k;
int rig[N],lef[N];
int preb[N];
int cnt[N];

int getv(int l,int r){
	if (l<=r)return preb[r]-preb[l-1];
	return preb[r]-preb[l-1]+preb[n];
}

int main(){
	char s[N];
	scanf("%s",s+1);
	n=strlen(s+1);
	fo(i,1,n)a[i]=s[i]-'0';
	scanf("%s",s+1);
	fo(i,1,n)b[i]=s[i]-'0';
	fo(i,1,n)preb[i]=preb[i-1]+b[i];
	if (!preb[n]){
		fo(i,1,n)
		if (a[i]){
			printf("-1\n");
			return 0;
		}
		printf("0\n");
		return 0;
	}
	int w=0;
	fo(i,1,n)if (b[i]){w=i;break;}
	rig[n]=(1-b[n])*w;fd(i,n-1,1)rig[i]=(1-b[i])*(rig[i+1]+1);
	fd(i,n,1)if (b[i]){w=i;break;}
	lef[1]=(1-b[1])*(n-w+1);fo(i,2,n)lef[i]=(1-b[i])*(lef[i-1]+1);
	int ans=1e+9;
	fo(l,-n+1,n-1){
		k=0;int v=0;
		fo(i,1,n){
			if (a[i]&&!b[(i+n-l-1)%n+1]){
				int x=(i+n-l-1)%n+1;
				if (l>=0&&getv(x,i)==0){p[++k].x=rig[i];p[k].y=lef[x];}
				if (l<0&&getv(i,x)==0){p[++k].x=lef[i];p[k].y=rig[x];}
			}
			if (a[i]!=b[(i+n-l-1)%n+1])v++;
		}
		fo(i,0,n)cnt[i]=0;
		sort(p+1,p+1+k);
		fo(i,1,k)cnt[p[i].y]++;
		int w=n;
		int mv=0;
		while(w&&!cnt[w])w--;
		mv=w*2;
		fo(i,1,k){
			cnt[p[i].y]--;
			while(w&&!cnt[w])w--;
			mv=min(mv,w*2+p[i].x*2);
		}
		mv+=v+abs(l);
		ans=min(ans,mv);
	}
	printf("%d\n",ans);
	return 0;
}

Submission Info

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:53:17: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
  scanf("%s",s+1);
                 ^
./Main.cpp:56:17: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
  scanf("%s",s+1);
                 ^

Judge Result