Submission #1939130

---

Source Code Expand

#include<stdio.h>
#include<math.h>
#include<algorithm>
#include<queue>
#include<deque>
#include<string>
#include<string.h>
#include<vector>
#include<set>
#include<map>
#include<bitset>
#include<stdlib.h>
#include<cassert>
using namespace std;
const long long mod=1000000007;
const long long inf=mod*mod;
const long long d2=500000004;
const double EPS=1e-6;
const double PI=acos(-1.0);
int ABS(int a){return max(a,-a);}
long long ABS(long long a){return max(a,-a);}
char A[8100];
char B[8100];
int sum[8100];
int main(){
	scanf("%s%s",A,B);
	int n=strlen(A);
	bool dame=true;
	for(int i=0;i<3*n;i++){
		A[i+n]=A[i];
		B[i+n]=B[i];
		if(B[i]=='1')dame=false;
	}
	set<int>S;
	for(int i=0;i<n*4;i++){
		if(B[i]=='1')S.insert(i);
		sum[i+1]=sum[i]+B[i]-'0';
	}

	int ret=mod;
	for(int i=0;i<n;i++){
		if(dame){
			bool ok=true;
			for(int j=0;j<n;j++)if(A[i+j]!=B[j])ok=false;
			if(ok)ret=0;
			continue;
		}
		vector<pair<int,int> >v;
		int tmp=0;
		for(int j=0;j<n;j++){
			if(A[i+j]!=B[j]){
				tmp++;
				int L=n+j;
				int R=n+i+j;
				if(sum[R+1]==sum[L]){
					int prev=*(--(S.lower_bound(L)));
					int nx=*(S.lower_bound(R));
					v.push_back(make_pair(prev-L,nx-R));
				}
			}
		}
		std::sort(v.begin(),v.end());
		int cur=mod;
		if(v.size()==0)cur=0;
		int ri=0;
		for(int j=0;j<v.size();j++){
			cur=min(cur,-v[j].first*2+ri*2);
			ri=max(ri,v[j].second);
		}
		cur=min(cur,ri*2);
		ret=min(ret,tmp+i+cur);
	//	printf("%d %d %d\n",tmp,i,cur);
		if(i==0)continue;
		v.clear();
		for(int j=0;j<n;j++){
			if(A[i+j]!=B[j]){
				int R=2*n+j;
				int L=n+i+j;
				if(sum[R+1]==sum[L]){
					int prev=*(--(S.lower_bound(L)));
					int nx=*(S.lower_bound(R));
					v.push_back(make_pair(prev-L,nx-R));
				}
			}
		}
		std::sort(v.begin(),v.end());
		cur=mod;
		if(v.size()==0)cur=0;
		ri=0;
		for(int j=0;j<v.size();j++){
			cur=min(cur,-v[j].first*2+ri*2);
			ri=max(ri,v[j].second);
		}
		cur=min(cur,ri*2);
		ret=min(ret,tmp+n-i+cur);
	//	printf("%d %d %d\n",tmp,n-i,cur);
	}
	if(ret==mod){
		ret=-1;
	}
	printf("%d\n",ret);
}

Submission Info

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:26: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