Submission #1625826

---

Source Code Expand

#include <bits/stdc++.h>
using namespace std;
string A, B;
int n;
const int N = 100000;
int L[N], R[N], mx[N];
int ans = N;
int main()
{
    cin >> A >> B;
    n = A.size();
    int G = 0;
    for (int i = 0; i < n; ++ i)
        if (B[i] == '1') G = 1;
    if (!G && A != B)
    {
        cout << -1 << endl;
        return 0;
    }
    B = B + B + B;
    for (int i = 0; i < n * 3; ++ i)
        if (B[i] == '1' || i == 0) L[i] = i;
        else L[i] = L[i - 1];
    for (int i = n * 3 - 1; ~i; -- i)
        if (B[i] == '1' || i == n * 3 - 1) R[i] = i;
        else R[i] = R[i + 1];
    for (int i = -n + 1; i <= n - 1; ++ i)
    {
        int cnt = 0;
        for (int j = 0; j <= n; ++ j) mx[j] = 0;
        for (int j = 0; j < n; ++ j)
            if (A[j] != B[n + j + i])
            {
                cnt ++;
                int ll = max(n + j - L[n + j] + min(0, i), 0);
                int rr = max(R[n + j] - n - j - max(0, i), 0);
                mx[ll + 1] = max(mx[ll + 1], rr);
            }
        for (int j = n; j >= 0; -- j) mx[j] = max(mx[j], mx[j + 1]);
        for (int j = 0; j <= n; ++ j)
            ans = min(ans, abs(i) + j * 2 + mx[j + 1] * 2 + cnt);
    }
    cout << ans;
}

Submission Info

Judge Result