Submission #1765688

---

Source Code Expand

#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define rep1(i,n) for(int i=1;i<=(int)(n);i++)
#define all(c) c.begin(),c.end()
#define pb push_back
#define fs first
#define sc second
#define show(x) cout << #x << " = " << x << endl
#define chmin(x,y) x=min(x,y)
#define chmax(x,y) x=max(x,y)
using namespace std;
template<class S,class T> ostream& operator<<(ostream& o,const pair<S,T> &p){return o<<"("<<p.fs<<","<<p.sc<<")";}
template<class T> ostream& operator<<(ostream& o,const vector<T> &vc){o<<"sz = "<<vc.size()<<endl<<"[";for(const T& v:vc) o<<v<<",";o<<"]";return o;}
 
string sa,sb;
const int MN = 2010;
int a[MN],b[MN];
int N;
 
int needl[MN],needr[MN];
 
int calc(int L,int R,int i){
	chmax(L,i);
	int res = R*2 + L + (L-i);
	return res;
}
 
int solve(){
	rep(i,N){
		for(int t=0;;t++){
			int j = (i-t+N)%N;
			if(b[j]){
				needl[i] = t;
				break;
			}
		}
	}
	rep(i,N){
		for(int t=0;;t++){
			int j = (i+t)%N;
			if(b[j]){
				needr[i] = t;
				break;
			}
		}
	}
	int res = 1e9;
	rep(i,N){
		vector<int> difs;
		rep(x,N){
			if(a[(i+x)%N]!=b[x]) difs.pb((i+x)%N);
		}
		using P = pair<int,int>;
		vector<P> vp;
		for(int d:difs){
			if(needl[d]<=i) continue;
			vp.pb(P(needl[d],needr[d]));
		}
		sort(all(vp),greater<P>());
 
		int tmp = 1e9;
		int L = N-1, R = 0;
 
		for(P p:vp){
			L = p.fs;
			chmin(tmp,calc(L,R,i));
			chmax(R,p.sc);
		}
		L = 0;
		chmin(tmp,calc(L,R,i));
 
		if(vp.empty()) tmp = i;
 
		tmp += difs.size();
 
		chmin(res,tmp);
	}
	return res;
}
 
int main(){
	cin>>sa>>sb;
	N = sa.size();
	rep(i,N){
		a[i] = sa[i]=='1';
		b[i] = sb[i]=='1';
	}
	if(sb == string(N,'0')){
		if(sa == string(N,'0')) puts("0");
		else puts("-1");
		return 0;
	}
	int ans = 1e9;
	rep(tt,2){
		chmin(ans,solve());
		reverse(a,a+N);
		reverse(b,b+N);
	}
	cout<<ans<<endl;
}

Submission Info

Judge Result