Submission #1549295

---

Source Code Expand

#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=a;i<b;i++)
#define rrep(i,a,b) for(int i=a;i>=b;i--)
#define fore(i,a) for(auto &i:a)
#pragma GCC optimize ("-O3")
using namespace std; void _main(); int main() { cin.tie(0); ios::sync_with_stdio(false); _main(); }
//---------------------------------------------------------------------------------------------------
/*---------------------------------------------------------------------------------------------------
　　　　　　　　　　　 ∧＿∧  
　　　　　 ∧＿∧ 　（´<_｀ ）　 Welcome to My Coding Space!
　　　　 （ ´_ゝ`）　/　 ⌒i     
　　　　／　　　＼　 　  |　|     
　　　 /　　 /￣￣￣￣/　　|  
　 ＿_(__ﾆつ/　    ＿/ .| .|＿＿＿＿  
　 　　　＼/＿＿＿＿/　（u　⊃  
---------------------------------------------------------------------------------------------------*/


#define INF INT_MAX/2
string A, B;
int N;
//---------------------------------------------------------------------------------------------------
int isng() {
    if (count(B.begin(), B.end(), '1')) return 0;
    if (count(A.begin(), A.end(), '1')) return 1;
    return 0;
}
//---------------------------------------------------------------------------------------------------
int g(vector<pair<int, int>> &v) {
    sort(v.begin(), v.end(), greater<pair<int, int>>());
    int res = INF, rmax = 0;
    fore(p, v) {
        res = min(res, p.first + rmax);
        rmax = max(rmax, p.second);
    }
    res = min(res, rmax);
    return res;
}
//---------------------------------------------------------------------------------------------------
int pre[2020], post[2020], sm[2020];
int f(int d) {
    int firs = -1;
    int last = 0;
    rep(i, 0, N) {
        if (firs < 0 && B[i] == '1') firs = i;
        if (B[i] == '1') last = i;
    }

    int p = last;
    rep(i, 0, N) {
        pre[i] = p;
        if (B[i] == '1') p = i;
    }
    p = firs;
    rrep(i, N - 1, 0) {
        post[i] = p;
        if (B[i] == '1') p = i;
    }

    sm[0] = 0;
    if (B[0] == '1') sm[0] = 1;
    rep(i, 1, N) {
        if (B[i] == '1') sm[i] = sm[i - 1] + 1;
        else sm[i] = sm[i - 1];
    }

    vector<pair<int, int>> v;
    int res = 0;
    rep(i, 0, N) {
        if (A[i] == B[(i + d) % N]) continue;
        res++;

        int a = i, b = (i + d) % N;
        int ss = -1;
        if (a <= b) {
            ss = sm[b];
            if (a) ss -= sm[a - 1];
        } else {
            ss = sm[N - 1];
            if (a) ss -= sm[a - 1];
            ss += sm[b];
        }
        if (ss) continue;

        int k = pre[i];
        int L = i - k;
        if (L < 0) L += N;

        int l = post[(i + d) % N];
        int R = l - (i + d) % N;
        if (R < 0) R += N;

        v.push_back({ L, R });
    }
    res += 2 * g(v) + d;

    return res;
}
//---------------------------------------------------------------------------------------------------
int solve() {
    int ans = INF;
    rep(d, 0, N * 2) ans = min(ans, f(d));
    return ans;
}
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> A >> B;
    N = A.length();

    if (isng()) {
        printf("-1\n");
        return;
    }

    int ans = INF;
    ans = solve();
    reverse(A.begin(), A.end());
    reverse(B.begin(), B.end());
    ans = min(ans, solve());
    cout << ans << endl;
}

Submission Info

Judge Result