Submission #1543570

---

Source Code Expand

#include <bits/stdc++.h>
#define fi first
#define se second
#define pb push_back
#define fio ios::sync_with_stdio(0),cin.tie(0),cout.tie(0)
using namespace std;
typedef pair<int,int> pii;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef long long ll;

const int N = 2005;
string a,b;
int n;

int pl[N],pr[N];
int pfl[N],pfr[N];

vector<pii> v;

int main() {
	fio;
	cin >> a >> b;
	n = a.size();
	int last = -1;
	for(int i = 0; i < 2*n; ++i) {
		if(b[i%n] == '1')
			last = i;
		if(i >= n)
			pl[i-n] = i-last;
	}
	if(last == -1) {
		printf("-1\n");
		return 0;
	}
	last = 2*n;
	for(int i = 2*n-1; i >= 0; --i) {
		if(b[i%n] == '1')
			last = i;
		if(i < n)
			pr[i] = last-i;
	}
	int ans = 1<<20;
	for(int s = -n; s < n; ++s) {
		string c = a;
		for(int i = 0; i < n; ++i) {
			int j = (i+s+n)%n;
			c[i] = a[j];
		}
		v.clear();
		// cout << "shift " << s << " -> " << a << " vs " << b <<  endl;
		for(int i = 0; i < n; ++i) {
			if(c[i] != b[i]) {
				v.emplace_back(pl[i],pr[i]);
				// cout << i << " -> " << v.back().fi << " " << v.back().se << endl;
			}
		}
		int base_l=0,base_r=0;
		if(s < 0) base_l = -s;
		if(s > 0) base_r = s;
		sort(v.begin(),v.end());
		pfl[0] = pfr[0] = 0;
		for(int i = 1; i <= v.size(); ++i) {
			pfl[i] = max(pfl[i-1],v[i-1].se);
			pfr[i] = max(pfr[i-1],v[v.size()-i].se);
		}
		//iter on max l
		for(int i = 0; i <= v.size(); ++i) {
			int max_l = pfl[i], max_r = pfr[v.size()-i];
			int r = v.size();
			r += 2*(max(base_r,max_r) - base_r);
			r += base_r;
			r += 2*(max(base_l,max_l) - base_l);
			r += base_l;
			ans = min(ans,r);
			// cout << base_l << " " << base_r << endl;
			// cout << s << " to " << a << " makes " << max_l << ", " << max_r <<  " : " << r << endl;
		}
	}
	printf("%d\n",ans);
}

Submission Info

Judge Result