Submission #1540293

---

Source Code Expand

#include <bits/stdc++.h>
using ll = long long;
using ld = long double;
using namespace std;

string s1;
string s2;


const int MAXN = 2001;

int l[MAXN], r[MAXN];

pair <int, int> a[MAXN];
int ac = 0;
int n;

int m(int x) {
    x %= n;
    return (x >= 0) ? x : x + n;
}

int main() {
#ifdef PAUNSVOKNO
	freopen("input.txt", "r", stdin); freopen("output.txt", "w", stdout);
#endif
	ios_base::sync_with_stdio(false); cout.setf(ios::fixed); cout.precision(20);
    cin >> s1 >> s2;
    n = s1.length();
    int c1 = 0, c2 = 0;
    for (int i = 0; i < n; i++) {
        if (s1[i] == '1') c1++;
    }

    for (int i = 0; i < n; i++)
        if (s2[i] == '1') c2++;

    if (c1 && !c2) {
        cout << -1 << "\n";
        return 0;
    }

    if (s1 == s2) {
        cout << 0 << "\n";
        return 0;
    }

    for (int i = 0; i < n; i++) {
        for (l[i] = 0; s2[m(i - l[i])] == '0'; l[i]++);
        for (r[i] = 0; s2[m(i + r[i])] == '0'; r[i]++);
    }

    int ans = MAXN * MAXN;

    for (int d = -n; d < n; d++) {
        ac = 0;
        int adc = 0;

        for (int i = 0; i < n; i++) {
            int ni = (i + n + d) % n;
            if (s1[i] == s2[ni]) continue;
            adc++;
            int nl = l[i] - max(-d, 0);
            int nr = r[i] - max(d, 0);
            if ((nl >= 0) && (nr >= 0)) a[ac++] = { nl, nr };
        }

        int cur = MAXN * MAXN;
        sort(a, a + ac);
        int mx = 0;

        for (int i = ac - 1; i >= 0; i--) {
            cur = min(cur, a[i].first + mx);
            mx = max(mx, a[i].second);
        }

        cur = min(cur, mx);

        ans = min(ans, abs(d) + cur * 2 + adc);
    }

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

Submission Info

Judge Result