Submission #1551657

---

Source Code Expand

#include <bits/stdc++.h>
using namespace std;
#define f first
#define s second
#define pb push_back
#define mp make_pair
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<double, int> pdi;
typedef pair<double, double> pdd;
const int MOD = 1000000007;
const int oo = 1000000001;
const int N = 2111;

string a , b;
int n, x[N];

vector<int>ones;

int nxt(int go) {
	vector<int>::iterator it = lower_bound(ones.begin(), ones.end(), go);
	if (it == ones.end())
		return n - go + ones[0];
	return *it - go;
}
int prv(int go) {
	vector<int>::iterator it = upper_bound(ones.begin(), ones.end(), go);
	if (it == ones.begin())
		return go + n - ones.back();
	return go - *(--it);
}
int main() {
	//freopen("input.txt", "r", stdin);
	cin >> a >> b;

	n = (int) a.size();
	int res = oo;
	for (int i = 0; i < b.size(); ++i)
		if (b[i] == '1')ones.push_back(i);
	if (ones.size() == 0) {
		int me = 0;
		for (int i = 0 ; i < a.size(); i++) {
			if (a[i] == '1')++me;
		}
		if (me == 0) {
			puts("0");
		} else {
			puts("-1");
		}
		return 0;
	}
	for (int d = -n ; d <= n-1; ++d) {
		memset(x, 0, sizeof x);
		int cnt = 0;
		for (int i = 0; i < a.size(); ++i) {
			int newJ = (i + d + n)%n;
			if (a[i] != b[newJ]) {
				++cnt;
				int nn = nxt(i);
				int pp = prv(i);
				x[nn] = max(x[nn], pp);
			}
		}
		if(!cnt){
			res = min(res,abs(d));
			continue;
		}
		int lft = 0;
		int best = oo, l = -oo, r = -oo;
		for (int rig = n - 1 ; rig >= 0 ; rig--) {
			res = min(res, 2 * (max(d,rig) - min(-lft,d)) - abs(d) + cnt);
			lft = max(lft, x[rig]);
		}
	}
	cout << res << endl;
	return 0;
}

Submission Info

Judge Result