Submission #5565240

---

Source Code Expand

#include <algorithm>
#include <iostream>
#include <vector>
#include <bitset>
#include <set>
using namespace std;

typedef long long ll;
typedef pair <ll, ll> pii;

const ll MAX_N = 4e3 + 6, inf = 1e9 + 7;
string A, B;
bitset <MAX_N> a, b, c, d, Lf[MAX_N], Rt[MAX_N];
vector <pii> seg;
ll n, ans = inf;
pii Arr[MAX_N];
ll mx[MAX_N];

bool cmp (pii a, pii b) {
	return a.second < b.second;
}

int main() {
    ios::sync_with_stdio(false), cin.tie(0);
    cin >> A >> B;
    n = A.size();

    for (ll i = 0; i < n; i++) {
        a[i] = (A[n - i - 1] == '1');
        b[i] = (B[n - i - 1] == '1');
        d[i] = true;
    }
    ll tmp = b.count() + a.count();
    if (b.count() == 0) {
    	if (a.count() == 0)
    		cout << "0\n";
    	else
    		cout << "-1\n";

    	return 0;
    }

    for (ll i = 0; i < n; i++) {
    	ll ind = -1, cnt = 0;
    	for (ll j = i; ~j; j--, cnt++)
    		if (B[j] == '1') {
    			ind = j;
    			break;
    		}

    	if (ind == -1)
    		for (ll j = n - 1; ~j; j--, cnt++)
    			if (B[j] == '1') {
    				ind = j;
    				break;
    			}

    	Arr[i].first = cnt;
    	cnt = 0;
    	ind = -1;
    	for (ll j = i; j < n; j++, cnt++)
    		if (B[j] == '1') {
    			ind = j;
    			break;
    		}

    	if (ind == -1)
    		for (ll j = 0; j < n - 1; j++, cnt++)
    			if (B[j] == '1') {
    				ind = j;
    				break;
    			}

    	Arr[i].second = cnt;
  		if (A[i] == '1')
  			seg.push_back({Arr[i].second, Arr[i].first});
    }

    sort(seg.begin(), seg.end());
    for (ll i = seg.size() - 1; ~i; i--)
    	mx[i] = max(mx[i + 1], seg[i].second);

    for (ll len = 0; len < n; len++) {
    	ll res = inf;
    	for (ll i = len; i < n; i++) {
    		ll ind = upper_bound(seg.begin(), seg.end(), pii(i, inf)) - seg.begin();
    		res = min(res, i + (i - len) + (mx[ind] << 1));
    	}

        c = a;
        c = (c >> len) | ((c << (n - len)) & d);

        res += tmp - ((b & c).count() << 1);
        ans = min(ans, res);
    }

    seg.clear();
    for (int i = 0; i < n; i++)
    	if (A[i] == '1')
    		seg.push_back(Arr[i]);

	sort(seg.begin(), seg.end());
    for (ll i = seg.size() - 1; ~i; i--)
    	mx[i] = max(mx[i + 1], seg[i].second);

    for (ll len = 0; len < n; len++) {
    	ll res = inf;
    	for (ll i = len; i < n; i++) {
    		ll ind = upper_bound(seg.begin(), seg.end(), pii(i, inf)) - seg.begin();
    		res = min(res, i + (i - len) + (mx[ind] << 1));
    	}

        c = a;
        c = ((c << len) & d) | ((c << len) >> n);

        res += tmp - ((b & c).count() << 1);
        ans = min(ans, res);
    }

	cout << ans << "\n";
    return 0;
}

Submission Info

Judge Result